Chandoo, Maurice
On the Implicit Graph Conjecture
Abstract
The implicit graph conjecture states that every sufficiently small, hereditary graph class has a labeling scheme with a polynomialtime 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 polynomialtime 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 firstorder 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:123:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6438},
URN = {urn:nbn:de:0030drops64389},
doi = {10.4230/LIPIcs.MFCS.2016.23},
annote = {Keywords: adjacency labeling scheme, complexity classes, diagonalization, logic}
}
2016
Keywords: 

adjacency labeling scheme, complexity classes, diagonalization, logic 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

2016 