3 Search Results for "Chandoo, Maurice"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.31
Tight Bounds on Adjacency Labels for Monotone Graph Classes

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

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
A class of graphs admits an adjacency labeling scheme of size b(n), if the vertices in each of its n-vertex graphs can be assigned binary strings (called labels) of length b(n) so that the adjacency of two vertices can be determined solely from their labels. We give bounds on the size of adjacency labels for every family of monotone (i.e., subgraph-closed) classes with a "well-behaved" growth function between 2^Ω(n log n) and 2^O(n^{2-δ}) for any δ > 0. Specifically, we show that for any function f: ℕ → ℝ satisfying log n ⩽ f(n) ⩽ n^{1-δ} for any fixed δ > 0, and some sub-multiplicativity condition, there are monotone graph classes with growth 2^O(nf(n)) that do not admit adjacency labels of size at most f(n) log n. On the other hand, any such class does admit adjacency labels of size O(f(n)log n). Surprisingly this bound is a Θ(log n) factor away from the information-theoretic bound of Ω(f(n)). Our bounds are tight upto constant factors, and the special case when f = log implies that the recently-refuted Implicit Graph Conjecture [Hatami and Hatami, FOCS 2022] also fails within monotone classes. We further show that the Implicit Graph Conjecture holds for all monotone small classes. In other words, any monotone class with growth rate at most n! cⁿ for some constant c > 0, admits adjacency labels of information-theoretic order optimal size. In fact, we show a more general result that is of independent interest: any monotone small class of graphs has bounded degeneracy. We conjecture that the Implicit Graph Conjecture holds for all hereditary small classes.
Cite as

Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. Tight Bounds on Adjacency Labels for Monotone Graph Classes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ICALP.2024.31,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor and Zhukovskii, Maksim},
  title =	{{Tight Bounds on Adjacency Labels for Monotone Graph Classes}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.31},
  URN =		{urn:nbn:de:0030-drops-201741},
  doi =		{10.4230/LIPIcs.ICALP.2024.31},
  annote =	{Keywords: Adjacency labeling, degeneracy, monotone classes, small classes, factorial classes, implicit graph conjecture}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.23
On the Implicit Graph Conjecture

Authors: Maurice Chandoo

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
The implicit graph conjecture states that every sufficiently small, hereditary graph class has a labeling scheme with a polynomial-time computable label decoder. We approach this conjecture by investigating classes of label decoders defined in terms of complexity classes such as P and EXP. For instance, GP denotes the class of graph classes that have a labeling scheme with a polynomial-time computable label decoder. Until now it was not even known whether GP is a strict subset of GR where R is the class of recursive languages. We show that this is indeed the case and reveal a strict hierarchy akin to classical complexity. We also show that classes such as GP can be characterized in terms of graph parameters. This could mean that certain algorithmic problems are feasible on every graph class in GP. Lastly, we define a more restrictive class of label decoders using first-order logic that already contains many natural graph classes such as forests and interval graphs. We give an alternative characterization of this class in terms of directed acyclic graphs. By showing that some small, hereditary graph class cannot be expressed with such label decoders a weaker form of the implicit graph conjecture could be disproven.
Cite as

Maurice Chandoo. On the Implicit Graph Conjecture. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chandoo:LIPIcs.MFCS.2016.23,
  author =	{Chandoo, Maurice},
  title =	{{On the Implicit Graph Conjecture}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.23},
  URN =		{urn:nbn:de:0030-drops-64389},
  doi =		{10.4230/LIPIcs.MFCS.2016.23},
  annote =	{Keywords: adjacency labeling scheme, complexity classes, diagonalization, logic}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.26
Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace

Authors: Maurice Chandoo

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
We compute a canonical circular-arc representation for a given circular-arc (CA) graph which implies solving the isomorphism and recognition problem for this class. To accomplish this we split the class of CA graphs into uniform and non-uniform ones and employ a generalized version of the argument given by Köbler et al. (2013) that has been used to show that the subclass of Helly CA graphs can be canonized in logspace. For uniform CA graphs our approach works in logspace and in addition to that Helly CA graphs are a strict subset of uniform CA graphs. Thus our result is a generalization of the canonization result for Helly CA graphs. In the non-uniform case a specific set Omega of ambiguous vertices arises. By choosing the parameter k to be the cardinality of Omega this obstacle can be solved by brute force. This leads to an O(k + log(n)) space algorithm to compute a canonical representation for non-uniform and therefore all CA graphs.
Cite as

Maurice Chandoo. Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chandoo:LIPIcs.STACS.2016.26,
  author =	{Chandoo, Maurice},
  title =	{{Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.26},
  URN =		{urn:nbn:de:0030-drops-57275},
  doi =		{10.4230/LIPIcs.STACS.2016.26},
  annote =	{Keywords: graph isomorphism, canonical representation, parameterized algorithm}
}
  • Refine by Author
  • 2 Chandoo, Maurice
  • 1 Bonnet, Édouard
  • 1 Duron, Julien
  • 1 Sylvester, John
  • 1 Zamaraev, Viktor
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph theory

  • Refine by Keyword
  • 1 Adjacency labeling
  • 1 adjacency labeling scheme
  • 1 canonical representation
  • 1 complexity classes
  • 1 degeneracy
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2016
  • 1 2024

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact