Skip to main content

Research Repository

Advanced Search

Partitioning graphs into connected parts

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

Authors

P. van 't Hof

G.J. Woeginger



Contributors

Pim van 't Hof dcs3pv@durham.ac.uk
Other

Abstract

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified 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 for any n-vertex Pℓ-free graph. For ℓ=6, its running time is . We modify this algorithm to solve the Longest Path Contractibility problem for P6-free graphs in time.

Citation

Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009). Partitioning graphs into connected parts. Theoretical Computer Science, 410(47-49), 4834-4843. https://doi.org/10.1016/j.tcs.2009.06.028

Journal Article Type Article
Publication Date Nov 1, 2009
Deposit Date Oct 14, 2009
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 410
Issue 47-49
Pages 4834-4843
DOI https://doi.org/10.1016/j.tcs.2009.06.028
Keywords Graph partition, Edge contraction, Path, Exact algorithm.
Public URL https://durham-repository.worktribe.com/output/1523871


You might also like



Downloadable Citations