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



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 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 P 6-free graphs in time.

Citation

Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009). Partitioning graphs into connected parts. In Computer science - theory and applications (143-154). https://doi.org/10.1007/978-3-642-03351-3_15

Conference Name Fourth International Computer Science Symposium in Russia (CSR 2009).
Conference Location Novosibirsk, Russia
Start Date Aug 18, 2009
End Date Aug 23, 2009
Publication Date Aug 1, 2009
Deposit Date Oct 15, 2009
Publisher Springer Verlag
Pages 143-154
Series Title Lecture notes in computer science
Series Number 5675
Book Title Computer science - theory and applications.
DOI https://doi.org/10.1007/978-3-642-03351-3_15
Public URL https://durham-repository.worktribe.com/output/1161004
Publisher URL http://www.springerlink.com/content/1432738112785766/


You might also like



Downloadable Citations