id: 05649473
dt: a
an: 05649473
au: Paulusma, Daniël; van Rooij, Johan M.M.
ti: On partitioning a graph into two connected subgraphs.
so: Dong, Yingfei (ed.) et al., Algorithms and computation. 20th international
    symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16‒18, 2009.
    Proceedings. Berlin: Springer (ISBN 978-3-642-10630-9/pbk). Lecture
    Notes in Computer Science 5878, 1215-1224 (2009).
py: 2009
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-10631-6_122
ab: Summary: 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\backslash (Z _{1} \cup Z _{2})$. We present an
    ${\mathcal O}^*(1.2051^n)$ time algorithm that solves it for this graph
    class. As a consequence, we can also solve this problem in ${\mathcal
    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 ${\mathcal
    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.
rv: