Definable Tree Decompositions
Definable Tree Decompositions
复制标题
可定义的树分解
DOI：
10.1109/lics.2008.10
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Martin Grohe
中科院分区：
文献类型：
--
作者：
Martin Grohe
我们引入了图的可定义树分解的概念。实际上，图的可定义树分解不仅仅是树分解，而是一个更复杂的结构，它代表了图的许多不同的树分解。它在图中可由某种逻辑的公式元组来定义。本文只研究在不动点逻辑中可定义的树分解。我们说一个可定义的树分解是在一类图上，如果分解的碎片在这个类中。我们证明了两个将图的树分解的可定义性结果提升到整个图的一般定理。这些结果统一了前人关于平面图和有界树宽图的不动点可定义性和描述复杂性理论的研究成果，并证明了所有不带k5次元的图在不动点逻辑中是可定义的，并且证明了带计数的不动点逻辑在这类图上占有多项式时间。
We introduce a notion of definable tree decompositions of graphs. Actually, a definable 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 K5-minor is definable infixed-point logic and that fixed-point logic with counting captures polynomial time on this class.