Partitioning graphs into connected parts

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationComputer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings
EditorsAnna E. Frid, Andrey Morozov, Andrey Rybalchenko, Klaus W. Wagner
PublisherSpringer Singapore
Pages143-154
Number of pages12
ISBN (Electronic)978-3-642-03351-3
ISBN (Print)978-3-642-03350-6
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk, Russian Federation
Duration: 18 Aug 200923 Aug 2009
Conference number: 4

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5675

Conference

Conference4th International Computer Science Symposium in Russia, CSR 2009
Abbreviated titleCSR 2009
CountryRussian Federation
CityNovosibirsk
Period18/08/0923/08/09

Fingerprint Dive into the research topics of 'Partitioning graphs into connected parts'. Together they form a unique fingerprint.

Cite this