On the complexity of finding iso- and other morphisms for partial k-trees
On the complexity of finding iso- and other morphisms for partial k-trees
复制标题
DOI：
10.1016/0012-365x(92)90687-b
复制
发表时间：
1992-10
期刊：
影响因子：
--
通讯作者：
J. Matoušek;R. Thomas
中科院分区：
文献类型：
--
作者：
J. Matoušek;R. Thomas
决定输入图 H,G 是否 H⩽G（其中 ⩽ 是“同构于子图”、“同构于诱导子图”、“同构于细分”、“同构于收缩”或它们的组合）的问题是 NP 完全的。我们讨论当G被限制为偏k树（用其他术语来说：树宽⩽k，bek可分解，维度⩽k）时这些问题的复杂性。在这种限制下，问题通常仍然是 NP 完全的，但是在对 H 施加一些自然限制的情况下存在多项式算法，例如当 H 具有有界度时。我们还给出了限制于部分 k 树（具有 n 部分输入）的不相交连接路径问题的多项式时间算法。
The problems to decide whetherH⩽Gfor input graphsH,Gwhere ⩽ is ‘isomorphic to a subgraph’, ‘isomorphic to an induced subgraphs’, ‘isomorphic to a subdivision’, ‘isomorphic to a contraction’ or their combination, are NP-complete. We discuss the complexity of these problems whenGis restricted to be a partialk-tree (in other terminology: to have tree-width ⩽k, to bek-decomposable, to have dimension ⩽k). Under this restriction the problems are still NP-complete in general, but there are polynomial algorithms under some natural restrictions imposed onH, for example whenHhas bounded degrees.We also give a polynomial time algorithm for thendisjoint connecting paths problem restricted to partialk-trees (withnpart of input).