Partitioning graphs into connected parts

Pim van 't Hof; Daniël Paulusma; Gerhard J. Woeginger

doi:10.1007/978-3-642-03351-3_15

Partitioning graphs into connected parts

Pim van 't Hof, Daniël Paulusma, Gerhard J. Woeginger

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

3 Citations (Scopus)

Abstract

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing pre-specified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Path Contractibility problem asks for the largest integer ℓ for which an input graph can be contracted to the path P ℓ on ℓ vertices. We show that the computational complexity of the Longest Path Contractibility problem restricted to P ℓ-free graphs jumps from being polynomially solvable to being NP-hard at ℓ= 6, while this jump occurs at ℓ= 5 for the 2-Disjoint Connected Subgraphs problem. We also present an exact algorithm that solves the 2-Disjoint Connected Subgraphs problem faster than O∗(2n) for any n-vertex P ℓ-free graph. For ℓ= 6, its running time is O∗(1.5790n) . We modify this algorithm to solve the Longest Path Contractibility problem for P 6-free graphs in O∗(1.5790n) time.

Original language	English
Title of host publication	Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings
Editors	Anna E. Frid, Andrey Morozov, Andrey Rybalchenko, Klaus W. Wagner
Publisher	Springer
Pages	143-154
Number of pages	12
ISBN (Electronic)	978-3-642-03351-3
ISBN (Print)	978-3-642-03350-6
DOIs	https://doi.org/10.1007/978-3-642-03351-3_15
Publication status	Published - 2009
Externally published	Yes
Event	4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk, Russian Federation Duration: 18 Aug 2009 → 23 Aug 2009 Conference number: 4

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5675

Conference

Conference	4th International Computer Science Symposium in Russia, CSR 2009
Abbreviated title	CSR 2009
Country/Territory	Russian Federation
City	Novosibirsk
Period	18/08/09 → 23/08/09

Access to Document

10.1007/978-3-642-03351-3_15

Cite this

van 't Hof, P., Paulusma, D., & Woeginger, G. J. (2009). Partitioning graphs into connected parts. In A. E. Frid, A. Morozov, A. Rybalchenko, & K. W. Wagner (Eds.), Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings (pp. 143-154). (Lecture Notes in Computer Science; Vol. 5675). Springer. https://doi.org/10.1007/978-3-642-03351-3_15

van 't Hof, Pim ; Paulusma, Daniël ; Woeginger, Gerhard J. / Partitioning graphs into connected parts. Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings. editor / Anna E. Frid ; Andrey Morozov ; Andrey Rybalchenko ; Klaus W. Wagner. Springer, 2009. pp. 143-154 (Lecture Notes in Computer Science).

@inproceedings{669c4b5151bb467cb9db7243841e282c,

title = "Partitioning graphs into connected parts",

abstract = "The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing pre-specified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Path Contractibility problem asks for the largest integer ℓ for which an input graph can be contracted to the path P ℓ on ℓ vertices. We show that the computational complexity of the Longest Path Contractibility problem restricted to P ℓ-free graphs jumps from being polynomially solvable to being NP-hard at ℓ= 6, while this jump occurs at ℓ= 5 for the 2-Disjoint Connected Subgraphs problem. We also present an exact algorithm that solves the 2-Disjoint Connected Subgraphs problem faster than O∗(2n) for any n-vertex P ℓ-free graph. For ℓ= 6, its running time is O∗(1.5790n) . We modify this algorithm to solve the Longest Path Contractibility problem for P 6-free graphs in O∗(1.5790n) time.",

author = "{van 't Hof}, Pim and Dani{\"e}l Paulusma and Woeginger, {Gerhard J.}",

year = "2009",

doi = "10.1007/978-3-642-03351-3_15",

language = "English",

isbn = "978-3-642-03350-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "143--154",

editor = "Frid, {Anna E.} and Andrey Morozov and Andrey Rybalchenko and Wagner, {Klaus W.}",

booktitle = "Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings",

address = "Germany",

note = "4th International Computer Science Symposium in Russia, CSR 2009, CSR 2009 ; Conference date: 18-08-2009 Through 23-08-2009",

}

van 't Hof, P, Paulusma, D & Woeginger, GJ 2009, Partitioning graphs into connected parts. in AE Frid, A Morozov, A Rybalchenko & KW Wagner (eds), Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5675, Springer, pp. 143-154, 4th International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russian Federation, 18/08/09. https://doi.org/10.1007/978-3-642-03351-3_15

Partitioning graphs into connected parts. / van 't Hof, Pim; Paulusma, Daniël; Woeginger, Gerhard J.
Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings. ed. / Anna E. Frid; Andrey Morozov; Andrey Rybalchenko; Klaus W. Wagner. Springer, 2009. p. 143-154 (Lecture Notes in Computer Science; Vol. 5675).

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

TY - GEN

T1 - Partitioning graphs into connected parts

AU - van 't Hof, Pim

AU - Paulusma, Daniël

AU - Woeginger, Gerhard J.

N1 - Conference code: 4

PY - 2009

Y1 - 2009

N2 - The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing pre-specified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Path Contractibility problem asks for the largest integer ℓ for which an input graph can be contracted to the path P ℓ on ℓ vertices. We show that the computational complexity of the Longest Path Contractibility problem restricted to P ℓ-free graphs jumps from being polynomially solvable to being NP-hard at ℓ= 6, while this jump occurs at ℓ= 5 for the 2-Disjoint Connected Subgraphs problem. We also present an exact algorithm that solves the 2-Disjoint Connected Subgraphs problem faster than O∗(2n) for any n-vertex P ℓ-free graph. For ℓ= 6, its running time is O∗(1.5790n) . We modify this algorithm to solve the Longest Path Contractibility problem for P 6-free graphs in O∗(1.5790n) time.

AB - The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing pre-specified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Path Contractibility problem asks for the largest integer ℓ for which an input graph can be contracted to the path P ℓ on ℓ vertices. We show that the computational complexity of the Longest Path Contractibility problem restricted to P ℓ-free graphs jumps from being polynomially solvable to being NP-hard at ℓ= 6, while this jump occurs at ℓ= 5 for the 2-Disjoint Connected Subgraphs problem. We also present an exact algorithm that solves the 2-Disjoint Connected Subgraphs problem faster than O∗(2n) for any n-vertex P ℓ-free graph. For ℓ= 6, its running time is O∗(1.5790n) . We modify this algorithm to solve the Longest Path Contractibility problem for P 6-free graphs in O∗(1.5790n) time.

U2 - 10.1007/978-3-642-03351-3_15

DO - 10.1007/978-3-642-03351-3_15

M3 - Conference contribution

SN - 978-3-642-03350-6

T3 - Lecture Notes in Computer Science

SP - 143

EP - 154

BT - Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings

A2 - Frid, Anna E.

A2 - Morozov, Andrey

A2 - Rybalchenko, Andrey

A2 - Wagner, Klaus W.

PB - Springer

T2 - 4th International Computer Science Symposium in Russia, CSR 2009

Y2 - 18 August 2009 through 23 August 2009

ER -

van 't Hof P, Paulusma D, Woeginger GJ. Partitioning graphs into connected parts. In Frid AE, Morozov A, Rybalchenko A, Wagner KW, editors, Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings. Springer. 2009. p. 143-154. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-03351-3_15

Partitioning graphs into connected parts

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this