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.

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, December). Finding contractions and induced minors in chordal graphs via disjoint paths. Presented at 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 22nd International Symposium on Algorithms and Computation, ISAAC 2011
• Publication Date: Jan 1, 2011
• Deposit Date: Dec 6, 2011
• Print ISSN: 0302-9743
• 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