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



Abstract

Suppose a graph G is given with two vertex-disjoint sets of vertices Z1 and Z2. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z1 and Z2, 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 Z1 and Z2 each contain a connected set that dominates all vertices in V∖(Z1∪Z2). We present an O∗(1.2051n) time algorithm that solves it for this graph class. As a consequence, we can also solve this problem in O∗(1.2051n) time for the classes of n-vertex P6-free graphs and split graphs. This is an improvement upon a recent O∗(1.5790n) 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. (2011). On partitioning a graph into two connected subgraphs. Theoretical Computer Science, 412(48), 6761-6769. https://doi.org/10.1016/j.tcs.2011.09.001

Journal Article Type Article
Publication Date Nov 1, 2011
Deposit Date Dec 6, 2011
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 412
Issue 48
Pages 6761-6769
DOI https://doi.org/10.1016/j.tcs.2011.09.001
Keywords Disjoint connected subgraphs, Dominating set, Exact algorithm.
Public URL https://durham-repository.worktribe.com/output/1524749


You might also like



Downloadable Citations