Skip to main content

Research Repository

Advanced Search

On partitioning a graph into two connected subgraphs

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

Authors

J. M. M. Rooij van



Contributors

Y. Dong
Editor

D.-Z. Du
Editor

I. Ibarra
Editor

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). On partitioning a graph into two connected subgraphs. In Y. Dong, D. Du, & I. Ibarra (Eds.), Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings (1215-1224). https://doi.org/10.1007/978-3-642-10631-6_122

Conference Name 20th International Symposium on Algorithms and Computation (ISAAC 2009)
Conference Location Honolulu, Hawaii, United States
Start Date Dec 16, 2009
End Date Dec 18, 2009
Publication Date Dec 1, 2009
Deposit Date Dec 15, 2009
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/