Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n
The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z 1,Z 2, asks whether it is possible to find disjoint sets A 1,A 2, such that Z 1?A 1, Z 2?A 2 and A 1,A 2 induce connected subgraphs. While the naive algorithm runs in O(2 n n O(1)) time, solutions with complexity of form O((2??) n ) have been found only for special graph classes (vantHof etal. inTheor. Comput. Sci. 410(4749):48344843, 2009; Paulusma and van Rooij in Theor. Comput. Sci. 412(48):67616769, 2011). In this paper we present an O(1.933 n ) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2 n 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.
2-disjoint connected subgraphs 2 n barrier kernelization exact algorithms exponential time hypothesis