On the complexity of finding iso- and other morphisms for partial k-trees

AbstractThe problems to decide whether H⩽G for input graphs H, G where ⩽ 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 when G is restricted to be a partial k-tree (in other terminology: to have tree-width ⩽k, to be k-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 on H, for example when H has bounded degrees.We also give a polynomial time algorithm for the n disjoint connecting paths problem restricted to partial k-trees (with n part of input)