On partitioning a graph into two connected subgraphs |
| |
Authors: | Danië l Paulusma,Johan M.M. van Rooij |
| |
Affiliation: | a Department of Computer Science, University of Durham, Science Laboratories, South Road, Durham DH1 3LE, United Kingdomb Department of Information and Computing Sciences, Universiteit Utrecht, PO Box 80.089, 3508TB Utrecht, The Netherlands |
| |
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. |
| |
Keywords: | Disjoint connected subgraphs Dominating set Exact algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|