Solving the 2-disjoint connected subgraphs problem faster than 2ⁿ

Abstract

The 2-DISJOINT CONNECTED SUBGRAPHS problem, given a graph along with two disjoint sets of terminals Z1,Z2, asks whether it is possible to find disjoint sets A1,A2, such that Z1 ⊆ A1, Z2 ⊆ A2 and A1,A2 induce connected subgraphs. While the naive algorithm runs in O(2nnO(1)) time, solutions with complexity of form O((2 − ε)n) have been found only for special graph classes (van ’t Hof et al. in Theor. Comput. Sci. 410(47–49):4834–4843, 2009; Paulusma and van Rooij in Theor. Comput. Sci. 412(48):6761–6769, 2011). In this paper we present an O(1.933n) algorithm for 2-DISJOINT CONNECTED SUBGRAPHS in general case, thus breaking the 2n barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel.