Partitioning graphs into connected parts

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

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, August). Partitioning graphs into connected parts. Presented at Fourth International Computer Science Symposium in Russia (CSR 2009)., Novosibirsk, Russia

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Fourth International Computer Science Symposium in Russia (CSR 2009).
• Start Date: Aug 18, 2009
• End Date: Aug 23, 2009
• Publication Date: Aug 1, 2009
• Deposit Date: Oct 15, 2009
• Print ISSN: 0302-9743
• 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/