## Partitioning graphs into connected parts

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

*Theoretical Computer Science*, vol. 410, no. 47-49, pp. 4834-4843, 2009.

[__DOI__]
[__Preprint__]

A preliminary version of this paper appeared in the proceedings of CSR 2009, the 4th International Computer Science Symposium in Russia (held on August 18-23, 2009 in Novosibirsk, Russia), *Lecture Notes in Computer Science*, vol. 5675, pp. 143-154, 2009.

[DOI]

This paper has been presented at
BCTCS 2009,
the 25th British Colloquium for Theoretical Computer Science (held on April 6-9, 2009 at the University of Warwick).

[__Slides__]

### Abstract:

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two disjoint connected subgraphs containing predefined 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 *k* for which an input graph can be contracted to the path *P _{k}* on

*k*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-complete at

_{k}*k*=6, while this jump occurs at

*k*=5 for the 2-Disjoint Connected Subgraphs problem. We also present an exact algorithm that solves the 2-Disjoint Connected Subgraphs problem in

*O*

^{*}(1.5790

*) time for*

^{n}*P*

_{6}-free graphs, and show how this algorithm can be modified to solve the Longest Path Contractibility problem for

*P*

_{6}-free graphs in in

*O*

^{*}(1.5790

*) time.*

^{n}