Isomorphism for Graphs of Bounded Distance Width
Isomorphism for Graphs of Bounded Distance Width
复制标题
有界距离宽度图的同构
作者：
K. Yamazaki;H. Bodlaender;B. D. Fluiter;D. Thilikos
抽象的。在本文中，我们研究有界树宽、有界度或有界带宽图上的图同构问题。对于有界树宽、路径宽度或带宽的图，图同构可以在多项式时间内求解，但指数取决于树宽、路径宽度或带宽。因此，我们寻找可以建立“固定参数易处理”多项式时间算法的特殊情况。我们引入了一些新的、自然的图参数：（有根）路径距离宽度，这是对带宽的限制，以及（有根）树距离宽度，这是对树宽度的限制。我们给出的算法可以在 O(n2) 时间内解决具有有界根路径距离宽度的图的图同构问题，以及在 O(n3) 时间内解决具有有界有根树距离宽度的图的问题。此外，我们表明计算图的路径距离宽度是 NP 困难的，但是当路径和树距离宽度受常数 k 限制时，可以在 O(nk+1) 时间内计算它们；有根路径或树距离宽度可以在 O(ne) 时间内计算出来。最后，我们研究新引入的参数与其他现有图参数之间的关系。
Abstract. In this paper we study the GRAPH ISOMORPHISM problem on graphs of bounded treewidth, bounded degree, or bounded bandwidth. GRAPH ISOMORPHISM can be solved in polynomial time for graphs of bounded treewidth, pathwidth, or bandwidth, but the exponent depends on the treewidth, pathwidth, or bandwidth. Thus, we look for special cases where ``fixed parameter tractable'' polynomial time algorithms can be established. We introduce some new and natural graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve GRAPH ISOMORPHISM in O(n2) time for graphs with bounded rooted path distance width, and in O(n3) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is NP-hard, but both path and tree distance width can be computed in O(nk+1) time, when they are bounded by a constant k; the rooted path or tree distance width can be computed in O(ne) time. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters.