Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Michał Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk · Algorithmica · 2013
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 (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.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.