On partitioning a graph into two connected subgraphs

作     者：Paulusma, Daniel van Rooij, Johan M. M. 

作者机构：Univ Durham Sci Labs Dept Comp Sci Durham DH1 3LE England Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2011年第412卷第48期

页      面：6761-6769页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：EPSRC [EP/D053633/1, EP/G043434/1] EPSRC [EP/D053633/1, EP/G043434/1] Funding Source: UKRI 

主　　题：Disjoint connected subgraphs Dominating set Exact algorithm 

摘      要：Suppose a graph G is given with two vertex-disjoint sets of vertices Z(1) and Z(2). Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z(1) and Z(2), 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(1) and Z(2) each contain a connected set that dominates all vertices in V\(Z(1)boolean OR Z(2)). 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. (C) 2011 Elsevier B.V. All rights reserved.