loading...
Definable Tree Decompositions
June 24-June 27
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2008.102008 23rd Annual IEEE Symposium on Lo ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.
Index Terms:
descriptive complexity, tree decomposition, fixed point logic
Citation:
Martin Grohe, "Definable Tree Decompositions," lics, pp.406-417, 2008 23rd Annual IEEE Symposium on Logic in Computer Science, 2008
Usage of this product signifies your acceptance of the Terms of Use.