Pim van 't Hof

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_k-free graphs jumps from being polynomially solvable to being NP-complete at 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 P₆-free graphs, and show how this algorithm can be modified to solve the Longest Path Contractibility problem for P₆-free graphs in in O^*(1.5790ⁿ) time.