Partitioning graphs into connected parts

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 O ∗ ( 2 n ) for any n -vertex P ℓ -free graph. For ℓ = 6, its running time is O ∗ ( 1. 579 0 n ). We modify this algorithm to solve the Longest Path Contractibility problem for P 6 -free graphs in O ∗ ( 1. 579 0 n ) time.

Authors

• Pim van ’t Hof
• Daniël Paulusma
• Gerhard J. Woeginger

Keywords

• Graph partition
• Edge contraction
• Path
• Exact algorithm