Partitioning graphs into connected parts

P. Hof, van 't, D. Paulusma, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)


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 l for which an input graph can be contracted to the path P l on l vertices. We show that the computational complexity of the LONGEST PATH CONTRACTIBILITY problem restricted to P l-free graphs jumps from being polynomially solvable to being NP-hard at l=¿6, while this jump occurs at l=¿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 l-free graph. For l=¿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)
EditorsA. Frid, A.S. Morozov, A. Rybalchenko, K.W. Wagner
Place of PublicationBerlin
ISBN (Print)978-3-642-03350-6
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


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

Cite this