Paper: Definable Tree Decompositions (at LICS 2008)

Authors: Martin Grohe

Abstract

We introduce a notion of definable tree decompositions of graphs. Actually, adefinable tree decomposition of a graph is not just a tree decomposition, but a more complicated structure that represents many different tree decompositions of the graph. It is definable in the graph by a tuple of formulas of some logic. In this paper, only study tree decomposition definable in fixed-point logic. We say that a definable tree decomposition is over a class of graphs if the pieces of the decomposition are in this class. We prove two general theorems lifting definability results from the pieces of a tree decomposition of a graph to the whole graph. Besides unifying earlier work on fixed-point definability and descriptive complexity theory on planar graphs and graphs of bounded tree width, these general results can be used to prove that the class of all graphs without a K_5-minor is definable infixed-point logic and that fixed-point logic with counting captures polynomialtime on this class.

BibTeX

  @InProceedings{Grohe-DefinableTreeDecomp,
    author = 	 {Martin Grohe},
    title = 	 {Definable Tree Decompositions},
    booktitle =  {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)},
    year =	 {2008},
    month =	 {June}, 
    pages =      {406--417},
    location =   {Pittsburgh, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }