Hof, P. van 't and Paulusma, Daniel and Woeginger, G. J. (2009) 'Partitioning graphs into connected parts.', in Computer science - theory and applications. Heidelberg: Springer, pp. 143-154. Lecture notes in computer science. (5675).
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.
|Item Type:||Book chapter|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-03351-3_15|
|Record Created:||15 Oct 2009 10:35|
|Last Modified:||02 Apr 2013 16:55|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|