License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.23
URN: urn:nbn:de:0030-drops-64389
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6438/
Go to the corresponding LIPIcs Volume Portal

Chandoo, Maurice

On the Implicit Graph Conjecture

pdf-format:
LIPIcs-MFCS-2016-23.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{chandoo:LIPIcs:2016:6438,
  author =	{Maurice Chandoo},
  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 =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6438},
  URN =		{urn:nbn:de:0030-drops-64389},
  doi =		{10.4230/LIPIcs.MFCS.2016.23},
  annote =	{Keywords: adjacency labeling scheme, complexity classes, diagonalization, logic}
}

Keywords: adjacency labeling scheme, complexity classes, diagonalization, logic
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI