5 Search Results for "Esperet, Louis"

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-dev.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-dev.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-dev.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-dev.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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.10
Distributed Coloring of Graphs with an Optimal Number of Colors

Authors: Étienne Bamas and Louis Esperet

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on coloring graphs of maximum degree Delta with at most Delta+1 colors (or Delta colors when some simple obstructions are forbidden). When Delta is sufficiently large and c >= Delta-k_Delta+1, for some integer k_Delta ~~ sqrt{Delta}-2, we give a distributed algorithm that given a c-colorable graph G of maximum degree Delta, finds a c-coloring of G in min{O((log Delta)^{13/12}log n), 2^{O(log Delta+sqrt{log log n})}} rounds, with high probability. The lower bound Delta-k_Delta+1 is best possible in the sense that for infinitely many values of Delta, we prove that when chi(G) <= Delta-k_Delta, finding an optimal coloring of G requires Omega(n) rounds. Our proof is a light adaptation of a remarkable result of Molloy and Reed, who proved that for Delta large enough, for any c >= Delta-k_Delta deciding whether chi(G) <= c is in P, while Embden-Weinert et al. proved that for c <= Delta-k_Delta-1, the same problem is NP-complete. Note that the sequential and distributed thresholds differ by one. Our first result covers the case where the chromatic number of the graph ranges between Delta-sqrt{Delta} and Delta+1. Our second result covers a larger range, but gives a weaker bound on the number of colors: For any sufficiently large Delta, and Omega(log Delta) <= k <= Delta/100, we prove that every graph of maximum degree Delta and clique number at most Delta-k can be efficiently colored with at most Delta-epsilon k colors, for some absolute constant epsilon >0, with a randomized algorithm running in O(log n/log log n) rounds with high probability.
Cite as

Étienne Bamas and Louis Esperet. Distributed Coloring of Graphs with an Optimal Number of Colors. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bamas_et_al:LIPIcs.STACS.2019.10,
  author =	{Bamas, \'{E}tienne and Esperet, Louis},
  title =	{{Distributed Coloring of Graphs with an Optimal Number of Colors}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.10},
  URN =		{urn:nbn:de:0030-drops-102496},
  doi =		{10.4230/LIPIcs.STACS.2019.10},
  annote =	{Keywords: Graph coloring, distributed algorithm, maximum degree}
}
  • Refine by Author
  • 4 Esperet, Louis
  • 2 Harms, Nathaniel
  • 1 Bamas, Étienne
  • 1 Klingelhoefer, Felix
  • 1 Kupavskii, Andrey
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Distributed algorithms
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph coloring
  • Show More...

  • Refine by Keyword
  • 1 Adjacency labeling schemes
  • 1 Algorithms
  • 1 Cartesian product
  • 1 Complexity
  • 1 Graph Coloring
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2022
  • 2 2023
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact