##
**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).

### MSC:

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 |

PDFBibTeX
XMLCite

\textit{J. Matoušek} and \textit{R. Thomas}, Discrete Math. 108, No. 1--3, 343--364 (1992; Zbl 0764.68128)

Full Text:
DOI

### References:

[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.