On partitioning a graph into two connected subgraphs

Paulusma, D.; Rooij van, J. M. M.

Abstract

Suppose a graph G is given with two vertex-disjoint sets of vertices Z₁ and Z₂. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z₁ and Z₂, respectively? This problem is known as the 2-Disjoint Connected Subgraphs problem. It is already NP-complete for the class of n-vertex graphs G = (V,E) in which Z₁ and Z₂ each contain a connected set that dominates all vertices in V\(Z₁ ∪ Z₂). We present an O^*(1.2051^n) time algorithm that solves it for this graph class. As a consequence, we can also solve this problem in O^*(1.2051^n) time for the classes of n-vertex P 6-free graphs and split graphs. This is an improvement upon a recent O^* (1.5790^n) time algorithm for these two classes. Our approach translates the problem to a generalized version of hypergraph 2-coloring and combines inclusion/exclusion with measure and conquer.

Citation

Paulusma, D., & Rooij van, J. M. M. (2009, December). On partitioning a graph into two connected subgraphs. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 20th International Symposium on Algorithms and Computation (ISAAC 2009)
• Start Date: Dec 16, 2009
• End Date: Dec 18, 2009
• Publication Date: Dec 1, 2009
• Deposit Date: Dec 15, 2009
• Print ISSN: 0302-9743
• Publisher: Springer Verlag
• Pages: 1215-1224
• Series Title: Lecture notes in computer science.
• Series Number: 5878
• Book Title: Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings.
• DOI: https://doi.org/10.1007/978-3-642-10631-6_122
• Public URL: https://durham-repository.worktribe.com/output/1160345
• Publisher URL: http://www.springerlink.com/content/u8740k7046427403/