On the complexity of finding iso- and other morphisms for partial \(k\)- trees. (English) Zbl 0764.68128

Summary: The problems to decide whether \(H\leq G\) for input graphs \(H\), \(G\) where \(\leq\) 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 \(\leq k\), to be \(k\)-decomposable, to have dimension \(\leq k)\). Using this restriction the problems are still NP- complete in general, but there are polynomial algorithms under some natural restrictions imposed in \(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).


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
Full Text: DOI


[1] Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebraic Discrete Methods, 8, 277-287 (1987) · Zbl 0611.05022
[2] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems on graphs embedded in \(k\)-trees, Discrete Appl. Math., 23, 11-24 (1989) · Zbl 0666.68067
[3] Bodlaender, H. L., Polynomial algorithm for graph is isomorphism and chromatic index on partial \(k\)-trees, (Technical Report (1988), University of Utrecht: University of Utrecht Utrecht) · Zbl 0651.68079
[4] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[5] Hopcroft, J. E.; Karp, R. E., An \(O(n^{52}\) algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 2, 225-231 (1973) · Zbl 0266.05114
[6] Karp, M., On the complexity of combinatorial problems, Networks, 5, 45-68 (1975) · Zbl 0324.05003
[7] Luks, E., Isomorphism of graphs of bounded valence can be tested in polynomial time, Proc. 21st IEEE Symp. on Foundations of Computer Science, 42-49 (1980) · Zbl 0493.68064
[8] Matoušek, J.; Thomas, R., Algorithms finding tree-decomposition of graphs, J. Algorithms, 12, 1-22 (1991) · Zbl 0712.68077
[9] Robertson, N.; Seymour, P. D., Graph minors II. Algorithmic aspects of tree-width, J. Algorithms, 7, 309-322 (1986) · Zbl 0611.05017
[10] N. Robertson and P.D. Seymour, Graph minors XIII. The disjoint paths problem, Manuscript.; N. Robertson and P.D. Seymour, Graph minors XIII. The disjoint paths problem, Manuscript. · Zbl 0823.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.