Skip to main content

Research Repository

Advanced Search

Finding contractions and induced minors in chordal graphs via disjoint paths

Belmonte, R.; Golovach, P. A.; Heggernes, P.; Hof van 't, P.; Kaminski, M.; Paulusma, D.

Authors

R. Belmonte

P. A. Golovach

P. Heggernes

P. Hof van 't

M. Kaminski



Contributors

T. Asano
Editor

S. Nakano
Editor

Y. Okamoto
Editor

O. Watanabe
Editor

Abstract

The k-Disjoint Paths problem, which takes as input a graph G and k pairs of specified vertices (s i ,t i ), asks whether G contains k mutually vertex-disjoint paths P i such that P i connects s i and t i , for i = 1,…,k. We study a natural variant of this problem, where the vertices of P i must belong to a specified vertex subset U i for i = 1,…,k. In contrast to the original problem, which is polynomial-time solvable for any fixed integer k, we show that this variant is NP-complete even for k = 2. On the positive side, we prove that the problem becomes polynomial-time solvable for any fixed integer k if the input graph is chordal. We use this result to show that, for any fixed graph H, the problems H-Contractibility and H-Induced Minor can be solved in polynomial time on chordal graphs. These problems are to decide whether an input graph G contains H as a contraction or as an induced minor, respectively.

Citation

Belmonte, R., Golovach, P. A., Heggernes, P., Hof van 't, P., Kaminski, M., & Paulusma, D. (2011). Finding contractions and induced minors in chordal graphs via disjoint paths. In T. Asano, S. Nakano, Y. Okamoto, & O. Watanabe (Eds.), Algorithms and Computation, 22nd International Symposium, ISAAC 2011, Yokohama, Japan, 5-8 December 2011 ; proceedings (110-119). https://doi.org/10.1007/978-3-642-25591-5_13

Conference Name 22nd International Symposium on Algorithms and Computation, ISAAC 2011
Conference Location Yokohama, Japan
Publication Date Jan 1, 2011
Deposit Date Dec 6, 2011
Pages 110-119
Series Title Lecture notes in computer science
Series Number 7074
Series ISSN 0302-9743,1611-3349
Book Title Algorithms and Computation, 22nd International Symposium, ISAAC 2011, Yokohama, Japan, 5-8 December 2011 ; proceedings.
ISBN 9783642255908
DOI https://doi.org/10.1007/978-3-642-25591-5_13
Public URL https://durham-repository.worktribe.com/output/1158711