Structure theorem and isomorphism test for graphs with excluded topological subgraphs
Structure theorem and isomorphism test for graphs with excluded topological subgraphs
复制标题
排除拓扑子图的图的结构定理和同构检验
DOI：
10.1145/2213977.2213996
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
D. Marx
中科院分区：
文献类型：
--
作者：
M. Grohe;D. Marx
本文将Robertson和Seymour关于不包含固定图H的图的结构定理推广到不包含H的图的拓扑子图。我们证明了，对于一个固定的H，每一个图不包括H作为一个拓扑子图有树分解，其中每个部分是“几乎嵌入”到一个固定的表面或有界的程度，除了一个有限数量的顶点。此外，这样的分解是可计算的算法是固定参数易处理的参数|H|我们给出了我们的结构定理的两个算法应用。为了说明结构定理的一个“典型”应用的机制，我们证明了在不包括H作为拓扑子图的图上，部分支配集（找到k个顶点的闭邻域具有最大值）可以在时间f（H，k）· nO（1）时间内求解.更重要的是，我们证明了在不包括H作为拓扑子图的图上，图同构可以在时间nf（H）中求解。这一结果统一和推广了两个已知的重要多项式时间可解的图同构的情况：有界度图和H-子自由图。这个结果的证明需要我们的结构定理的一个推广到不变的树状分解的上下文中。
We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph H as a minor to graphs excluding H as a topological subgraph. We prove that for a fixed H, every graph excluding H as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter |H|.We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a "typical" application of the structure theorem, we show that on graphs excluding H as a topological subgraph, Partial Dominating Set (find k vertices whose closed neighborhood has maximum size) can be solved in time f(H,k) • nO(1)time. More significantly, we show that on graphs excluding H as a topological subgraph, Graph Isomorphism can be solved in time nf(H). This result unifies and generalizes two previously known important polynomial-time solvable cases of Graph Isomorphism: bounded-degree graphs and H-minor free graphs. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition.
登录
查看更多内容
小图算法的简短证明-唯一联动定理-
DOI：
--
发表时间：
2010
期刊：
42nd ACM Symposium on Theory of Computing (STOC'10)
影响因子：
--
作者：
K.Kawarabayashi;P.Wollan
通讯作者：
P.Wollan
DOI：
--
发表时间：
2003
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour
小闭族的色数和列表色数的近似
DOI：
--
发表时间：
2006
期刊：
ACM Symposium on Theory of Computing (STOC' 06) 38
影响因子：
--
作者：
K.Kawarabayashi;B.Mohar
通讯作者：
B.Mohar
可定义的树分解
DOI：
10.1109/lics.2008.10
发表时间：
2008
期刊：
2008 23rd Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Martin Grohe
通讯作者：
Martin Grohe
k-可收缩图的同构。
影响因子：
--
作者：
G. Miller
通讯作者：
G. Miller