Finding contractions and induced minors in chordal graphs via disjoint paths

Rémy Belmonte; Petr A. Golovach; Pinar Heggernes; Pim van 't Hof; Marcin Kaminski; Daniël Paulusma

doi:10.1007/978-3-642-25591-5_13

Finding contractions and induced minors in chordal graphs via disjoint paths

Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kaminski, Daniël Paulusma

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

12 Citations (Scopus)

14 Downloads (Pure)

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.

Original language	English
Title of host publication	Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings
Editors	Takao Asano, Shin-Ichi Nakano, Yoshio Okamoto, Osamu Watanabe
Publisher	Springer
Pages	110-119
Number of pages	10
ISBN (Electronic)	978-3-642-25591-5
ISBN (Print)	978-3-642-25590-8
DOIs	https://doi.org/10.1007/978-3-642-25591-5_13
Publication status	Published - 2011
Event	22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan Duration: 5 Dec 2011 → 8 Dec 2011 Conference number: 22

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	7074

Conference

Conference	22nd International Symposium on Algorithms and Computation, ISAAC 2011
Abbreviated title	ISAAC 2011
Country/Territory	Japan
City	Yokohama
Period	5/12/11 → 8/12/11

Access to Document

10.1007/978-3-642-25591-5_13

Cite this

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

Belmonte, Rémy ; Golovach, Petr A. ; Heggernes, Pinar et al. / Finding contractions and induced minors in chordal graphs via disjoint paths. Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings. editor / Takao Asano ; Shin-Ichi Nakano ; Yoshio Okamoto ; Osamu Watanabe. Springer, 2011. pp. 110-119 (Lecture Notes in Computer Science).

@inproceedings{87ac2f47747742389985e8f16d4e899f,

title = "Finding contractions and induced minors in chordal graphs via disjoint paths",

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.",

author = "R{\'e}my Belmonte and Golovach, \{Petr A.\} and Pinar Heggernes and \{van 't Hof\}, Pim and Marcin Kaminski and Dani{\"e}l Paulusma",

year = "2011",

doi = "10.1007/978-3-642-25591-5\_13",

language = "English",

isbn = "978-3-642-25590-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "110--119",

editor = "Takao Asano and Shin-Ichi Nakano and Yoshio Okamoto and Osamu Watanabe",

booktitle = "Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings",

address = "Germany",

note = "22nd International Symposium on Algorithms and Computation, ISAAC 2011, ISAAC 2011 ; Conference date: 05-12-2011 Through 08-12-2011",

}

Belmonte, R, Golovach, PA, Heggernes, P, van 't Hof, P, Kaminski, M & Paulusma, D 2011, Finding contractions and induced minors in chordal graphs via disjoint paths. in T Asano, S-I Nakano, Y Okamoto & O Watanabe (eds), Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings. Lecture Notes in Computer Science, vol. 7074, Springer, pp. 110-119, 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan, 5/12/11. https://doi.org/10.1007/978-3-642-25591-5_13

Finding contractions and induced minors in chordal graphs via disjoint paths. / Belmonte, Rémy; Golovach, Petr A.; Heggernes, Pinar et al.
Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings. ed. / Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto; Osamu Watanabe. Springer, 2011. p. 110-119 (Lecture Notes in Computer Science; Vol. 7074).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Finding contractions and induced minors in chordal graphs via disjoint paths

AU - Belmonte, Rémy

AU - Golovach, Petr A.

AU - Heggernes, Pinar

AU - van 't Hof, Pim

AU - Kaminski, Marcin

AU - Paulusma, Daniël

N1 - Conference code: 22

PY - 2011

Y1 - 2011

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

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

U2 - 10.1007/978-3-642-25591-5_13

DO - 10.1007/978-3-642-25591-5_13

M3 - Conference contribution

SN - 978-3-642-25590-8

T3 - Lecture Notes in Computer Science

SP - 110

EP - 119

BT - Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings

A2 - Asano, Takao

A2 - Nakano, Shin-Ichi

A2 - Okamoto, Yoshio

A2 - Watanabe, Osamu

PB - Springer

T2 - 22nd International Symposium on Algorithms and Computation, ISAAC 2011

Y2 - 5 December 2011 through 8 December 2011

ER -

Belmonte R, Golovach PA, Heggernes P, van 't Hof P, Kaminski M, Paulusma D. Finding contractions and induced minors in chordal graphs via disjoint paths. In Asano T, Nakano SI, Okamoto Y, Watanabe O, editors, Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings. Springer. 2011. p. 110-119. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-25591-5_13

Finding contractions and induced minors in chordal graphs via disjoint paths

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this