DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.55

Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion

Authors: Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the graph satisfies P or not. Often, testers are restricted to a constant number of queries. While the graph properties for which there exists such a tester are somewhat well characterized in the dense graph model, it is not the case for sparse graphs. In this area, Czumaj and Sohler (FOCS’19) proved that H-freeness (i.e. the property of excluding the graph H as a subgraph) can be tested with constant queries on planar graphs as well as on graph classes excluding a minor. Using results from the sparsity toolkit, we propose a simpler alternative to the proof of Czumaj and Sohler, for a statement generalized to the broader notion of bounded expansion. That is, we prove that for any class 𝒞 with bounded expansion and any graph H, testing H-freeness can be done with constant query complexity on any graph G in 𝒞, where the constant depends on H and 𝒞, but is independent of G. While classes excluding a minor are prime examples of classes with bounded expansion, so are, for example, cubic graphs, graph classes with bounded maximum degree, or graphs of bounded book thickness. Additionally, random graphs with bounded average degree almost surely have bounded expansion.

Cite as

Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny. Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{humeau_et_al:LIPIcs.STACS.2026.55,
  author =	{Humeau, Samuel and Kant\'{e}, Mamadou Moustapha and Mock, Daniel and Picavet, Timoth\'{e} and Vigny, Alexandre},
  title =	{{Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.55},
  URN =		{urn:nbn:de:0030-drops-255441},
  doi =		{10.4230/LIPIcs.STACS.2026.55},
  annote =	{Keywords: Property testing, Sparsity, Bounded expansion, Treedepth}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.34

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right

Authors: Yuval Gil and Merav Parter

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In this setting, the verifier consists of n nodes connected by a communication graph G. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G satisfies a certain property (e.g., planarity) in a small number of rounds, and with a small communication bound, denoted as the proof size. Prior work by Naor, Parter and Yogev (SODA 2020) presented a DIP for planarity that uses three interaction rounds and a proof size of O(log n). Feuilloley et al. (PODC 2020) showed that the same can be achieved with a single interaction round and without randomization, by providing a proof labeling scheme with a proof size of O(log n). In a subsequent work, Bousquet, Feuilloley, and Pierron (OPODIS 2021) achieved the same bound for related graph families such as outerplanarity, series-parallel graphs, and graphs of treewidth at most 2. In this work, we design new DIPs that use exponentially shorter proofs compared to the state-of-the-art bounds. Our main results are: - There is a 5-round protocol with O(log log n) proof size for outerplanarity. - There is a 5-round protocol with O(log log n) proof size for verifying embedded planarity and O(log log n+log Δ) proof size for general planar graphs, where Δ is the maximum degree in the graph. In the former setting, it is assumed that an embedding of the graph is given (e.g., each node holds a clockwise orientation of its neighbors) and the goal is to verify that it is a valid planar embedding. The latter result should be compared with the non-interactive setting for which there is lower bound of Ω(log n) bits for graphs with Δ = O(1) by Feuilloley et al. (PODC 2020). - The non-interactive deterministic lower bound of Ω(log n) bits by Feuilloley et al. (PODC 2020) can be extended to hold even if the verifier is randomized. Moreover, the lower bound holds even with the assumption that the verifier’s randomness comes in the form of an unbounded random string shared among the nodes. We also show that our DIPs can be extended to protocols with similar bounds for verifying series-parallel graphs and graphs with tree-width at most 2. Perhaps surprisingly, our results demonstrate that the key technical barrier for obtaining o(log log n) labels for all our problems is a basic sorting verification task in which all nodes are embedded on an oriented path P ⊆ G and it is desired for each node to distinguish between its left and right G-neighbors.

Cite as

Yuval Gil and Merav Parter. New Distributed Interactive Proofs for Planarity: A Matter of Left and Right. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gil_et_al:LIPIcs.DISC.2025.34,
  author =	{Gil, Yuval and Parter, Merav},
  title =	{{New Distributed Interactive Proofs for Planarity: A Matter of Left and Right}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{34:1--34:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.34},
  URN =		{urn:nbn:de:0030-drops-248515},
  doi =		{10.4230/LIPIcs.DISC.2025.34},
  annote =	{Keywords: Distributed interactive proofs, Planar graphs}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.18

Complexity Landscape for Local Certification

Authors: Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

An impressive recent line of work has charted the complexity landscape of distributed graph algorithms. For many settings, it has been determined which time complexities exist, and which do not (in the sense that no local problem could have an optimal algorithm with that complexity). In this paper, we initiate the study of the landscape for space complexity of distributed graph algorithms. More precisely, we focus on the local certification setting, where a prover assigns certificates to nodes to certify a property, and where the space complexity is measured by the size of the certificates. Already for anonymous paths and cycles, we unveil a surprising landscape: - There is a gap between complexity O(1) and Θ(log log n) in paths. This is the first gap established in local certification. - There exists a property that has complexity Θ(log log n) in paths, a regime that was not known to exist for a natural property. - There is a gap between complexity O(1) and Θ(log n) in cycles, hence a gap that is exponentially larger than for paths. We then generalize our result for paths to the class of trees. Namely, we show that there is a gap between complexity O(1) and Θ(log log d) in trees, where d is the diameter. We finally describe some settings where there are no gaps at all. To prove our results we develop a new toolkit, based on various results of automata theory and arithmetic, which is of independent interest.

Cite as

Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Complexity Landscape for Local Certification. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.DISC.2025.18,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Zeitoun, S\'{e}bastien},
  title =	{{Complexity Landscape for Local Certification}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{18:1--18:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.18},
  URN =		{urn:nbn:de:0030-drops-248350},
  doi =		{10.4230/LIPIcs.DISC.2025.18},
  annote =	{Keywords: Local certification, proof-labeling schemes, locally checkable proofs, space complexity, distributed graph algorithms, complexity gap}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.58

Equality Is Far Weaker Than Constant-Cost Communication

Authors: Mika Göös, Nathaniel Harms, and Artur Riazanov

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract

We exhibit an n-bit communication problem with a constant-cost randomized protocol but which requires n^Ω(1) deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of Hatami and Hatami (SIGACT News 2024). It also gives a significantly simpler and quantitatively superior proof of the main result of Fang, Göös, Harms, and Hatami (STOC 2025), that constant-cost communication does not reduce to the k-Hamming Distance hierarchy.

Cite as

Mika Göös, Nathaniel Harms, and Artur Riazanov. Equality Is Far Weaker Than Constant-Cost Communication. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.APPROX/RANDOM.2025.58,
  author =	{G\"{o}\"{o}s, Mika and Harms, Nathaniel and Riazanov, Artur},
  title =	{{Equality Is Far Weaker Than Constant-Cost Communication}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.58},
  URN =		{urn:nbn:de:0030-drops-244246},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.58},
  annote =	{Keywords: Equality oracle, constant-cost communication, gamma-2 norm, spectral norm}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2025.16

Isometric-Universal Graphs for Trees

Authors: Edgar Baucher, François Dross, and Cyril Gavoille

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

We consider the problem of finding the smallest graph that contains two input trees each with at most n vertices preserving their distances. In other words, we look for an isometric-universal graph with the minimum number of vertices for two given trees. We prove that this problem can be solved in time O(n^{5/2}log{n}). We extend this result to forests instead of trees, and propose an algorithm with running time O(n^{7/2}log{n}). As a key ingredient, we show that a smallest isometric-universal graph of two trees essentially is a tree. Furthermore, we prove that these results cannot be extended. Firstly, we show that deciding whether there exists an isometric-universal graph with t vertices for three forests is NP-complete. Secondly, we show that any smallest isometric-universal graph cannot be a tree for some families of three trees. This latter result has implications for greedy strategies solving the smallest isometric-universal graph problem.

Cite as

Edgar Baucher, François Dross, and Cyril Gavoille. Isometric-Universal Graphs for Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baucher_et_al:LIPIcs.MFCS.2025.16,
  author =	{Baucher, Edgar and Dross, Fran\c{c}ois and Gavoille, Cyril},
  title =	{{Isometric-Universal Graphs for Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.16},
  URN =		{urn:nbn:de:0030-drops-241237},
  doi =		{10.4230/LIPIcs.MFCS.2025.16},
  annote =	{Keywords: tree, forest, isometric subgraph, universal graph, distance-preserving}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.86

Optimal Distance Labeling for Permutation Graphs

Authors: Paweł Gawrychowski and Wojciech Janczewski

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

A permutation graph is the intersection graph of a set of segments between two parallel lines. In other words, they are defined by a permutation π on n elements, such that u and v are adjacent if an only if u < v but π(u) > π(v). We consider the problem of computing the distances in such a graph in the setting of informative labeling schemes. The goal of such a scheme is to assign a short bitstring 𝓁(u) to every vertex u, such that the distance between u and v can be computed using only 𝓁(u) and 𝓁(v), and no further knowledge about the whole graph (other than that it is a permutation graph). This elegantly captures the intuition that we would like our data structure to be distributed, and often leads to interesting combinatorial challenges while trying to obtain lower and upper bounds that match up to the lower-order terms. For distance labeling of permutation graphs on n vertices, Katz, Katz, and Peleg [STACS 2000] showed how to construct labels consisting of 𝒪(log² n) bits. Later, Bazzaro and Gavoille [Discret. Math. 309(11)] obtained an asymptotically optimal bound by showing how to construct labels consisting of 9log{n}+𝒪(1) bits, and proving that 3log{n}-𝒪(log{log{n}}) bits are necessary. This however leaves a quite large gap between the known lower and upper bounds. We close this gap by showing how to construct labels consisting of 3log{n}+𝒪(1) bits.

Cite as

Paweł Gawrychowski and Wojciech Janczewski. Optimal Distance Labeling for Permutation Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 86:1-86:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ICALP.2025.86,
  author =	{Gawrychowski, Pawe{\l} and Janczewski, Wojciech},
  title =	{{Optimal Distance Labeling for Permutation Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{86:1--86:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.86},
  URN =		{urn:nbn:de:0030-drops-234632},
  doi =		{10.4230/LIPIcs.ICALP.2025.86},
  annote =	{Keywords: informative labeling, permutation graph, distance labeling}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.36

Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs

Authors: James Davies, Agelos Georgakopoulos, Meike Hatzel, and Rose McCarty

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

In this paper, we consider the class 𝒞^d of sphere intersection graphs in R^d for d ≥ 2. We show that for each integer t, the class of all graphs in 𝒞^d that exclude K_{t,t} as a subgraph has strongly sublinear separators. We also prove that 𝒞^d has asymptotic dimension at most 2d+2.

Cite as

James Davies, Agelos Georgakopoulos, Meike Hatzel, and Rose McCarty. Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.SoCG.2025.36,
  author =	{Davies, James and Georgakopoulos, Agelos and Hatzel, Meike and McCarty, Rose},
  title =	{{Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.36},
  URN =		{urn:nbn:de:0030-drops-231881},
  doi =		{10.4230/LIPIcs.SoCG.2025.36},
  annote =	{Keywords: Intersection graphs, strongly sublinear separators, asymptotic dimension}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.21

Adjacency Labeling Schemes for Small Classes

Authors: Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

A graph class admits an implicit representation if, for every positive integer n, its n-vertex graphs have a O(log n)-bit (adjacency) labeling scheme, i.e., their vertices can be labeled by binary strings of length O(log n) such that the presence of an edge between any pair of vertices can be deduced solely from their labels. The famous Implicit Graph Conjecture posited that every hereditary (i.e., closed under taking induced subgraphs) factorial (i.e., containing 2^O(n log n) n-vertex graphs) class admits an implicit representation. The conjecture was recently refuted [Hatami and Hatami, FOCS '22], and does not even hold among monotone (i.e., closed under taking subgraphs) factorial classes [Bonnet et al., ICALP '24]. However, monotone small (i.e., containing at most n! cⁿ many n-vertex graphs for some constant c) classes do admit implicit representations. This motivates the Small Implicit Graph Conjecture: Every hereditary small class admits an O(log n)-bit labeling scheme. We provide evidence supporting the Small Implicit Graph Conjecture. First, we show that every small weakly sparse (i.e., excluding some fixed bipartite complete graph as a subgraph) class has an implicit representation. This is a consequence of the following fact of independent interest proved in the paper: Every weakly sparse small class has bounded expansion (hence, in particular, bounded degeneracy). Second, we show that every hereditary small class admits an O(log³ n)-bit labeling scheme, which provides a substantial improvement of the best-known polynomial upper bound of n^(1-ε) on the size of adjacency labeling schemes for such classes. This is a consequence of another fact of independent interest proved in the paper: Every small class has neighborhood complexity O(n log n).

Cite as

Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev. Adjacency Labeling Schemes for Small Classes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ITCS.2025.21,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor},
  title =	{{Adjacency Labeling Schemes for Small Classes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.21},
  URN =		{urn:nbn:de:0030-drops-226493},
  doi =		{10.4230/LIPIcs.ITCS.2025.21},
  annote =	{Keywords: Adjacency labeling, degeneracy, weakly sparse classes, small classes, implicit graph conjecture}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2024.28

How Local Constraints Influence Network Diameter and Applications to LCL Generalizations

Authors: Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract

In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results have important consequences on the landscape of locally checkable labelings (LCL) on unbounded degree graphs, a case in which our lack of knowledge is in striking contrast with that of bounded degree graphs, that has been intensively studied recently. First, we show that the diameter of a tree can be controlled very precisely by a local checker (that is, a distributed decision algorithm that accepts a graph iff all nodes accept locally), granted that its checkability radius is at least 2 (and that the target diameter is not too close to n). As a corollary, we prove that the gaps in the landscape of LCLs (in bounded-degree graphs) basically disappear in unbounded degree graphs. Second, we prove that for checkers at distance 1, the maximum diameter can only be trivial (constant or linear), while the minimum diameter can in addition be Θ(log n) and Θ(n^(1/k)) for k ∈ ℕ. These functions interestingly coincide with the known regimes for LCLs. Third, we explore computational restrictions of local checkers. In particular, we introduce a class of checkers, that we call degree-myopic, that cannot distinguish perfectly the degrees of their neighbors. With these checkers, we show that the maximum diameter can only be O(1), Θ(√n), Θ((log n)/(log log n)), Θ(log n), or Ω(n). Since gaps do appear in the maximum diameter, one can hope that an interesting LCL landscape exists for restricted local checkers. In addition to the LCL motivation, we hope that our distributed lenses can help give a new point of view on how global structures, such as living beings, can be maintained by local phenomena; understanding the trade-off between the power of the checking and the possible resulting shapes.

Cite as

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. How Local Constraints Influence Network Diameter and Applications to LCL Generalizations. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 28:1-28:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2024.28,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Pierron, Th\'{e}o},
  title =	{{How Local Constraints Influence Network Diameter and Applications to LCL Generalizations}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{28:1--28:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.28},
  URN =		{urn:nbn:de:0030-drops-225643},
  doi =		{10.4230/LIPIcs.OPODIS.2024.28},
  annote =	{Keywords: Locally checkable labelings, network diameter, local checkers, LOCAL model}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2024.25

Better Boosting of Communication Oracles, or Not

Authors: Nathaniel Harms and Artur Riazanov

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract

Suppose we have a two-party communication protocol for f which allows the parties to make queries to an oracle computing g; for example, they may query an Equality oracle. To translate this protocol into a randomized protocol, we must replace the oracle with a randomized subroutine for solving g. If q queries are made, the standard technique requires that we boost the error of each subroutine down to O(1/q), leading to communication complexity which grows as q log q. For which oracles g can this naïve boosting technique be improved? We focus on the oracles which can be computed by constant-cost randomized protocols, and show that the naïve boosting strategy can be improved for the Equality oracle but not the 1-Hamming Distance oracle. Two surprising consequences are (1) a new example of a problem where the cost of computing k independent copies grows superlinear in k, drastically simplifying the only previous example due to Blais & Brody (CCC 2019); and (2) a new proof that Equality is not complete for the class of constant-cost randomized communication (Harms, Wild, & Zamaraev, STOC 2022; Hambardzumyan, Hatami, & Hatami, Israel Journal of Mathematics 2022).

Cite as

Nathaniel Harms and Artur Riazanov. Better Boosting of Communication Oracles, or Not. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{harms_et_al:LIPIcs.FSTTCS.2024.25,
  author =	{Harms, Nathaniel and Riazanov, Artur},
  title =	{{Better Boosting of Communication Oracles, or Not}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.25},
  URN =		{urn:nbn:de:0030-drops-222143},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.25},
  annote =	{Keywords: oracles, error reduction, communication complexity}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2024.48

Local Certification of Geometric Graph Classes

Authors: Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

The goal of local certification is to locally convince the vertices of a graph G that G satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view and their own unique identifier, they must decide whether G satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in n-vertex graphs, planarity can be certified locally with certificates of size O(log n), we show that several closely related graph classes require certificates of size Ω(n). This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of Ω(n^{1-δ}) for any δ > 0 on the size of the certificates, and an upper bound of O(n log n). The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.

Cite as

Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local Certification of Geometric Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{defrain_et_al:LIPIcs.MFCS.2024.48,
  author =	{Defrain, Oscar and Esperet, Louis and Lagoutte, Aur\'{e}lie and Morin, Pat and Raymond, Jean-Florent},
  title =	{{Local Certification of Geometric Graph Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{48:1--48:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.48},
  URN =		{urn:nbn:de:0030-drops-206042},
  doi =		{10.4230/LIPIcs.MFCS.2024.48},
  annote =	{Keywords: Local certification, proof labeling schemes, geometric intersection graphs}
}

Document

DOI: 10.4230/LIPIcs.ESA.2023.71

Coloring Tournaments with Few Colors: Algorithms and Complexity

Authors: Felix Klingelhoefer and Alantha Newman

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

A k-coloring of a tournament is a partition of its vertices into k acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring a 3-colorable graph with few colors, is to color a 2-colorable tournament with few colors. This problem does not seem to have been addressed before, although it is a special case of coloring a 2-colorable 3-uniform hypergraph with few colors, which is a well-studied problem with super-constant lower bounds. We present an efficient decomposition lemma for tournaments and show that it can be used to design polynomial-time algorithms to color various classes of tournaments with few colors, including an algorithm to color a 2-colorable tournament with ten colors. For the classes of tournaments considered, we complement our upper bounds with strengthened lower bounds, painting a comprehensive picture of the algorithmic and complexity aspects of coloring tournaments.

Cite as

Felix Klingelhoefer and Alantha Newman. Coloring Tournaments with Few Colors: Algorithms and Complexity. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{klingelhoefer_et_al:LIPIcs.ESA.2023.71,
  author =	{Klingelhoefer, Felix and Newman, Alantha},
  title =	{{Coloring Tournaments with Few Colors: Algorithms and Complexity}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.71},
  URN =		{urn:nbn:de:0030-drops-187247},
  doi =		{10.4230/LIPIcs.ESA.2023.71},
  annote =	{Keywords: Tournaments, Graph Coloring, Algorithms, Complexity}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2023.57

Optimal Adjacency Labels for Subgraphs of Cartesian Products

Authors: Louis Esperet, Nathaniel Harms, and Viktor Zamaraev

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract

For any hereditary graph class ℱ, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in ℱ. As a consequence, we show that, if ℱ admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then the classes of subgraphs and induced subgraphs of Cartesian products of graphs in ℱ do too. Our proof uses ideas from randomized communication complexity and hashing, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020].

Cite as

Louis Esperet, Nathaniel Harms, and Viktor Zamaraev. Optimal Adjacency Labels for Subgraphs of Cartesian Products. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 57:1-57:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{esperet_et_al:LIPIcs.ICALP.2023.57,
  author =	{Esperet, Louis and Harms, Nathaniel and Zamaraev, Viktor},
  title =	{{Optimal Adjacency Labels for Subgraphs of Cartesian Products}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{57:1--57:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.57},
  URN =		{urn:nbn:de:0030-drops-181093},
  doi =		{10.4230/LIPIcs.ICALP.2023.57},
  annote =	{Keywords: Adjacency labeling schemes, Cartesian product, Hypercubes}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.18

Sketching Distances in Monotone Graph Classes

Authors: Louis Esperet, Nathaniel Harms, and Andrey Kupavskii

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract

We study the problems of adjacency sketching, small-distance sketching, and approximate distance threshold (ADT) sketching for monotone classes of graphs. The algorithmic problem is to assign random sketches to the vertices of any graph G in the class, so that adjacency, exact distance thresholds, or approximate distance thresholds of two vertices u,v can be decided (with probability at least 2/3) from the sketches of u and v, by a decoder that does not know the graph. The goal is to determine when sketches of constant size exist. Our main results are that, for monotone classes of graphs: constant-size adjacency sketches exist if and only if the class has bounded arboricity; constant-size small-distance sketches exist if and only if the class has bounded expansion; constant-size ADT sketches imply that the class has bounded expansion; any class of constant expansion (i.e. any proper minor closed class) has a constant-size ADT sketch; and a class may have arbitrarily small expansion without admitting a constant-size ADT sketch.

Cite as

Louis Esperet, Nathaniel Harms, and Andrey Kupavskii. Sketching Distances in Monotone Graph Classes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{esperet_et_al:LIPIcs.APPROX/RANDOM.2022.18,
  author =	{Esperet, Louis and Harms, Nathaniel and Kupavskii, Andrey},
  title =	{{Sketching Distances in Monotone Graph Classes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.18},
  URN =		{urn:nbn:de:0030-drops-171406},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.18},
  annote =	{Keywords: adjacency labelling, informative labelling, distance sketching, adjacency sketching, communication complexity}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.58

Testability and Local Certification of Monotone Properties in Minor-Closed Classes

Authors: Louis Esperet and Sergey Norin

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

The main problem in the area of graph property testing is to understand which graph properties are testable, which means that with constantly many queries to any input graph G, a tester can decide with good probability whether G satisfies the property, or is far from satisfying the property. Testable properties are well understood in the dense model and in the bounded degree model, but little is known in sparse graph classes when graphs are allowed to have unbounded degree. This is the setting of the sparse model. We prove that for any proper minor-closed class 𝒢, any monotone property (i.e., any property that is closed under taking subgraphs) is testable for graphs from 𝒢 in the sparse model. This extends a result of Czumaj and Sohler (FOCS'19), who proved it for monotone properties with finitely many forbidden subgraphs. Our result implies for instance that for any integers k and t, k-colorability of K_t-minor free graphs is testable in the sparse model. Elek recently proved that monotone properties of bounded degree graphs from minor-closed classes that are closed under disjoint union can be verified by an approximate proof labeling scheme in constant time. We show again that the assumption of bounded degree can be omitted in his result.

Cite as

Louis Esperet and Sergey Norin. Testability and Local Certification of Monotone Properties in Minor-Closed Classes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{esperet_et_al:LIPIcs.ICALP.2022.58,
  author =	{Esperet, Louis and Norin, Sergey},
  title =	{{Testability and Local Certification of Monotone Properties in Minor-Closed Classes}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.58},
  URN =		{urn:nbn:de:0030-drops-163997},
  doi =		{10.4230/LIPIcs.ICALP.2022.58},
  annote =	{Keywords: Property testing, sparse model, local certification, minor-closed classes}
}

16 Search Results for "Esperet, Louis"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message