Algorithmica (2014) 70:195207
DOI 10.1007/s00453-013-9796-x
Solving the 2-Disjoint Connected Subgraphs Problem
Faster than 2n
Marek Cygan Marcin Pilipczuk
Micha Pilipczuk Jakub Onufry Wojtaszczyk
Received: 7 September 2012 / Accepted: 14 May 2013 / Published online: 31 May 2013
The Author(s) 2013. This article is published with open access at Springerlink.com
Abstract The 2-D ISJOINT C ONNECTED S UBGRAPHS 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(2n nO(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(4749):48344843, 2009; Paulusma and van Rooij
in Theor. Comput. Sci. 412(48):67616769, 2011). In this paper we present an
O(1.933n ) algorithm for 2-D ISJOINT C ONNECTED S UBGRAPHS 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.
Keywords Exact algorithms 2n barrier 2-Disjoint Connected Subgraphs
Kernelization Exponential Time Hypothesis
M. Cygan M. Pilipczuk
Institute of Informatics, University of Warsaw, Warsaw, Poland
M. Cygan
e-mail: cygan@mimuw.edu.pl
M. Pilipczuk
e-mail: malcin@mimuw.edu.pl
M. Pilipczuk ()
Department of Informatics, University of Bergen, Bergen, Norway
e-mail: michal.pilipczuk@ii.uib.no
J.O. Wojtaszczyk
Google Inc., Warsaw, Poland
e-mail: onufry@google.com
196
Algorithmica (2014) 70:195207
1 Introduction
It is commonly believed that no NP-complete problem is solvable in polynomial time.
However, while all NP-complete problems are equivalent with respect to polynomial
time reductions, they appear to be very different with respect to the best exponential time exact solutions. In particular, a number of NP-complete problems can be
solved much faster than the obvious algorithm that enumerates all possible solutions;
examples are I NDEPENDENT S ET [12], D OMINATING S ET [12, 21], C HROMATIC
N UMBER [3] and BANDWIDTH [6]. The race for the fastest exact algorithm inspired
several very interesting tools and techniques such as Fast Subset Convolution [2] and
Measure&Conquer [12] (for an overview of the field we refer the reader to a recent
book by Fomin and Kratsch [11]).
For several problems, including TSP, C HROMATIC N UMBER, P ERMANENT, S ET
C OVER, #H AMILTONIAN C YCLES and SAT, the currently best known time complexity is of the form O(2n nO(1) ), which is a result of applying dynamic programming over subsets, the inclusion-exclusion principle or a brute force search. The question remains, however, which of those problems are inherently so hard that it is not
possible to break the 2n barrier and which are just waiting for new tools and techniques still to be discovered. In particular, the hardness of the k-SAT problem is the
starting point for the Strong Exponential Time Hypothesis of Impagliazzo and Paturi [5, 15], which is used as an argument that other problems are hard [7, 9, 16,
17]. Recently, on the positive side, O(cn ) time algorithms for a constant c < 2 have
been developed for S CHED [8], M AXIMUM I NDUCED P LANAR S UBGRAPH [13] and
(a major breakthrough in the field) for the undirected version of the H AMILTONIAN
C YCLE problem [1]. In most cases breaking the 2n -barrier gives an O(cn )-time algorithm with c significantly smaller than 2.
In this paper we study the 2-D ISJOINT C ONNECTED S UBGRAPHS problem:
2-D ISJOINT C ONNECTED S UBGRAPHS
Input: An undirected graph G = (V , E) together with two disjoint subsets of vertices Z1 , Z2 V .
Task: Is it possible to find two disjoint subsets A1 and A2 of V , such that Z1 A1 ,
Z2 A2 and G[A1 ], G[A2 ] are connected?
We call vertices from Z1 Z2 terminals and all other vertices non-terminals.
A general version of this problem (that is when we consider arbitrary number of
sets) was used as one of tools in the celebrated result of Robertson and Seymour [19],
that the M INOR C ONTAINMENT problem can be solved in polynomial time for every
fixed pattern graph H. In literature, the solution (A1 , A2 ) is sometimes required to
be a partition of V . Note that this does not simplify the problem: in our setting, if G
is connected, the superfluous vertices can always be attached to one of the sets A1
or A2 , while otherwise the instance is trivial.
Previous Work Gray et al. [14] show that the 2-D ISJOINT C ONNECTED S UB GRAPHS problem is NP-complete even for the class of planar graphs. The motivation for this variant comes from an application in computational geometry, namely
Algorithmica (2014) 70:195207
197
finding a realization of an imprecise terrain that minimizes the total number of local
minima and local maxima. Furthermore, van t Hof et al. [22] proved that the problem
remains NP-complete even if |Z1 | = 2.
From the exact exponential time algorithms perspective the authors in [22] show
that one can solve 2-D ISJOINT C ONNECTED S UBGRAPHS in O((2 ())n ) time
for any n-vertex P -free graph. This line of research was continued by Paulusma and
van Rooij [18], where the authors present an algorithm with O(1.2051n ) running
time complexity for P6 -free graphs and split graphs.
Our Results In [18] Paulusma and van Rooij ask whether it is possible to solve the
2-D ISJOINT C ONNECTED S UBGRAPHS problem in general graphs faster than using
the trivial O(2n nO(1) ) algorithm. In this paper we answer this question affirmatively
and present an O(1.933n ) time and polynomial space algorithm. Our approach is
based on the branch and reduce technique and a combinatorial study of the case when
the number of terminal vertices is small.
Theorem 1 One can solve the 2-D ISJOINT C ONNECTED S UBGRAPHS problem in
O(1.933n ) running time and polynomial space.
To break the 2n barrier we heavily use the fact that in the instance size n we count
not only non-terminals but also terminal vertices. Observe that the naive brute-force
algorithm, which for every partition of V \ (Z1 Z2 ) checks whether A1 \ Z1 , A2 \ Z2
can be found within its sides, runs in O(2k nO(1) ) time, where k is the number of
non-terminals. Therefore, it is natural to ask whether it is possible to obtain also
an O((2 )k nO(1) ) algorithm. Using a recent hardness result (under the Strong
Exponential Time Hypothesis; see Sect. 2 for an exact statement) of Cygan et al. [9]
for the S ET S PLITTING problem, we show that this is not the case: breaking the 2k
barrier is hard.
Theorem 2 There does not exist an epsilon > 0 and an algorithm running in
O((2 )k |V |O(1) ) time for the 2-D ISJOINT C ONNECTED S UBGRAPHS problem
unless the Strong Exponential Time Hypothesis is false.
We should note that the Strong Exponential Time Hypothesis is a very strong
assumption, and not widely believed, as it is the case of its weaker cousin, the Exponential Time Hypothesis (which is still much stronger than the statement P = NP).
However, as noted in [16], SETH-based lower bounds still make sense: one should
probably wait with trying to break a SETH-hard barrier until a faster SAT algorithm
is discovered.
Since the naive O(2k nO(1) ) time algorithm for 2-D ISJOINT C ONNECTED S UB GRAPHS shows that the problem is fixed-parameter tractable, a usual next step is
to investigate the kernelization possibilities for the problem (see Sect. 2 for respective definitions). Using the kernelization hardness result of Dom et al. [10] for the
C OLOUR H ITTING S ET problem parameterized by the size of the universe we show
that 2-D ISJOINT C ONNECTED S UBGRAPHS parameterized by the number of nonterminal vertices is unlikely to admit a polynomial kernel.
198
Algorithmica (2014) 70:195207
Theorem 3 The 2-D ISJOINT C ONNECTED S UBGRAPHS problem parameterized
by the number of non-terminals does not admit a polynomial kernel unless NP
coNP/poly.
As a byproduct we prove a kernelization hardness result for S ET S PLITTING
parameterized by the size of the universe, which is of independent interest.
S ET S PLITTING
Input: A set system (F , U ), where F 2U .
Task: Does there exist a subset X U such that each set in F contains both an
element from X and from U \ X?
Theorem 4 The S ET S PLITTING problem parameterized by the universe size does
not admit a polynomial kernel unless NP coNP/poly.
Organization of the Paper In Sect. 2 we provide the reader with the necessary
definitions. Section 3 is devoted to the details of the O(1.933n ) algorithm for 2D ISJOINT C ONNECTED S UBGRAPHS, while in Sect. 4 we present the negative results for the parameterization by the number of non-terminals. Concluding remarks
are gathered in Sect. 5.
2 Preliminaries
Notation For an undirected graph G = (V , E) and a subset of vertices X V by
G[X] we denote the subgraph induced by X. An articulation point in G is a vertex,
whose removal increases the number of connected components of G.
For a universe U and two subsets X, Y U we say that X splits Y if Y X =
and Y (U \ X) = .
Parameterized Complexity In the parameterized complexity setting, an instance
comes with an integer parameter kformally, a parameterized problem Q is a subset
of N for some finite alphabet . We say that the problem is fixed parameter tractable (FPT) if there exists an algorithm solving any instance (x, k) in time
f (k)poly(|x|) for some (usually exponential) computable function f . It is known
that a problem is FPT iff it is kernelizable: a kernelization algorithm for a problem
Q takes an instance (x, k) and in time polynomial in |x| + k produces an equivalent
instance (x , k ) (i.e., (x, k) Q iff (x , k ) Q) such that |x | + k g(k) for some
computable function g. The function g is the size of the kernel, and if it is polynomial,
we say that Q admits a polynomial kernel.
The hardness of kernelization can be obtained in a reduction-like manner by
polynomial-time transformations from problems known to be hard to kernelize.
Definition 1 [4] Let P and Q be parameterized problems. We say that P is polynomial parameter reducible to Q, written P p Q, if there exists a polynomial time
computable function f : N N and a polynomial p, such that for
Algorithmica (2014) 70:195207
199
all (x, k) N the following holds: (x, k) P iff (x , k ) = f (x, k) Q and
k p(k). The function f is called a polynomial parameter transformation.
be the unpaTheorem 5 [4] Let P and Q be parameterized problems and P and Q
rameterized versions of P and Q respectively. Suppose that P is NP-hard and Q is
in NP. Assume there is a polynomial parameter transformation from P to Q. Then if
Q admits a polynomial kernel, so does P .
Exponential Time Hypothesis [5, 15] Let ck be the infimum of a set of reals c for
which there exists an algorithm solving the k-CNF-SAT problem in time O(cn ),
where n is the number of variables in the input formula. The Exponential Time Hypothesis (ETH) asserts that c3 > 1, whereas the Strong Exponential Time Hypothesis
(SETH) asserts that limk ck = 2. In particular, SETH implies that satisfiability of
an arbitrary boolean formula cannot be checked significantly faster than by trying all
possible assignments.
3 Algorithm
In this section we provide an algorithm solving the 2-D ISJOINT C ONNECTED S UB GRAPHS problem in O(1.933n ) time, where n is the total number of vertices in the input graph. Recall that in the 2-D ISJOINT C ONNECTED S UBGRAPHS problem the vertices were divided into three groupsA1 , A2 and V \ (A1 A2 ). The algorithm will
be simpler to present if we merge A2 with V \ (A1 A2 ). This means that we drop the
condition that A2 is connected, requiring instead that all vertices from Z2 are in the
same connected component of G[A2 ]. Formally, we consider the following problem:
M ODIFIED 2-D ISJOINT C ONNECTED S UBGRAPHS
Input: An undirected graph G = (V , E) together with two disjoint subsets of vertices Z1 , Z2 V .
Task: Is it possible to partition V into sets A1 , A2 , with Z1 A1 and Z2 A2 , such
that G[A1 ] is connected and all the vertices of Z2 lie in the same connected component of G[A2 ]?
First notice that if we fix A1 , then checking the correctness of a partition is a
polynomial-time operation.
Let = 0.0493. If |Z1 | + |Z2 | |V |, we can simply iterate over all possible choices of A1 \ Z1 this is a subset of V \ (Z1 Z2 ), so we have an
O(2|V ||Z1 ||Z2 | nO(1) ) O(2(1)n nO(1) ) O(1.933n ) algorithm solving the problem. From now on we assume |Z1 | + |Z2 | < n. Additionally we assume that
|Z1 | |Z2 |, which means |Z1 | < n/2.
We will be looking for a set A1 which is minimal with respect to inclusion. Let
us fix one such set. Let G = G[A1 ]. Notice that any vertex r A1 \ Z1 has to be an
articulation point in G , otherwise we could move it from A1 to A2 and still have a
valid solution. We will prove the following lemma:
200
Algorithmica (2014) 70:195207
Lemma 1 Let H be any graph with at least 2 vertices. Let k be the number of vertices
of H that are not articulation points, and let l be the number of articulation points of
degree at least three. Then 3k 6 l.
The proof has been postponed to Sect. 3.2.
Let us call all the vertices of Z1 and those vertices of A1 with degree larger than 2
in G jointly branching points. As |Z1 | n/2, by Lemma 1 applied to G we have
that G contains at most 2n 6 branching points.
Notice that we can assume that no vertex in A1 \ Z1 is of degree 0 or 1 in G[A1 ]
(because, again, we could remove it to achieve a smaller solution)thus all the vertices that are not branching points have to be of degree two in G[A1 ].
We now pursue a branch and reduce algorithm. A state of our algorithm is an
instance (G = (V , E), Z1 , Z2 ) of the M ODIFIED 2-D ISJOINT C ONNECTED S UB GRAPHS problem, plus a set A2 Z2 of vertices that we have already chosen to be
in A2 . The running time of our algorithm depends on two numbers:
N = |V \ A2 |the number of vertices of the graph not yet chosen to A2 ;
Kthe upper limit on the number of branching points in the graph.
Formally, we describe a procedure solve(G, Z1 , Z2 , A2 , K) that either:
1. reports a valid solution (A1 , A2 ) to the M ODIFIED 2-D ISJOINT C ONNECTED
S UBGRAPHS problem, such that A2 A2 , or
2. reports NO, correctly claiming that the M ODIFIED 2-D ISJOINT C ONNECTED
S UBGRAPHS instance (G, Z1 , Z2 ) has no solution (A1 , A2 ), such that A2 A2
and A1 has at most K branching points.
Note that the outcomes above are not exclusive: if the input M ODIFIED 2-D ISJOINT
C ONNECTED S UBGRAPHS instance has a solution, but only with more than K
branching points, the algorithm can report any of the answers.
Let = (|Z1 | + |Z2 |)/|V |, recall we assume . The starting value of N is no
larger than (1 /2)|V |. Lemma 1 ensures us that solve(G, Z1 , Z2 , Z2 , 2|V | 6)
reports a solution if and only if the M ODIFIED 2-D ISJOINT C ONNECTED S UB GRAPHS instance (G, Z1 , Z2 ) is a YES-instance.
Let T (N, K) be the worst-case cost of executing our algorithm for given values of
N and K. We need to prove that T ((1 /2)n, 2n 6) 1.933n for any 0 .
We will also describe a similar procedure solve (G, Z1 , Z2 , A2 , K, w), where
in addition to the input graph as in the original problem, we have a single vertex w,
adjacent to some t Z1 , and we already decided that w A1 (we did not decide
whether w is a branching point or not). Let T (N, K) denote the worst-case complexity of executing our algorithm for given values of N and K in this case. We will
simultaneously prove the following two inequalities:
T (N, K) 1.5901N 8.109K ,
T (N, K) 0.3711 1.5901N 8.109K .
It is easy to check this suffices to prove Theorem 1. As all the inequalities presented
further are not tight within very small constants, the obtained bound on the running
Algorithmica (2014) 70:195207
201
time is in fact slightly better; therefore, we can suppress all the polynomial factors
using this error.
3.1 Reduction Rules
We provide a set of reduction rules. The algorithm at each point finds the lowestnumber reduction rule applicable and applies it. Finding and applying a single reduction rule will trivially be a polynomial-time operation.
During the algorithm we will assign vertices both to A1 and A2 . A feature of our
algorithm is that a vertex v can be assigned to A1 only if there is some w Z1 adjacent to it. When we assign v to A1 , we will represent this by contracting the edge vw.
Note that the resultant instance is fully equivalent to the originalif (A1 , A2 ) is
a valid solution in the reduced graph, then (A1 {v}, A2 ) is a valid solution in the
original graph, and conversely if (A1 , A2 ) is a valid solution in the original graph,
and v A1 , then (A1 \ v, A2 ) is a valid solution in the reduced graph.
If we find a solution in any of the branches, we return it as the witness of the
positive answer for the problem. If we find no solution, we return NO.
3.1.1 Reduction Rules for solve(G, Z1 , Z2 , A2 , K)
Reduction Rule 1 If there are two vertices from Z1 in different components of
G[V \ A2 ], return NO from this branch.
Reduction Rule 2 If |Z1 | = 1, we check whether all the vertices of Z2 lie in the same
connected component of G[V \ Z1 ]. If yes, we report a solution (Z1 , V \ Z1 ). If no,
we return NO from this branch.
Reduction Rule 3 If K < |Z1 |, we return NO from this branch.
Reduction Rule 4 If there are two adjacent vertices t, t Z1 , contract the edge tt
and reduce K by one.
Reduction Rule 5 If there is a vertex w adjacent to some t Z1 (necessarily
w
/ Z1 ), we branch. We will either put it in A2 in the solution, or choose it to be
a part of A1 and proceed to the second variant of the problem.
To check the complexity assumptions in this case, we verify that the running time
after applying the reduction rule is at most the claimed bound on T (N, K):
T (N 1, K) + T (N, K) 1.5901N 1 8.109K + 0.3711 1.5901N 8.109K
1.5901N 8.109K .
The correctness of all the above rules is trivial.
202
Algorithmica (2014) 70:195207
3.1.2 Reduction Rules for solve (G, Z1 , Z2 , A2 , K, w)
Recall that now we have a vertex w which we already know to be in A1 , and which
is adjacent to some t Z1 .
Reduction Rule 6 If w is adjacent to some vertex t Z1 other than t, we contract
the edges tw and t w, and decrease K by one.
Notice that as we contracted two vertices from Z1 into a single vertex in this case,
we have at least one branching point less in the reduced graph than in the original. To
check the complexity assumptions in this case, we verify that the running time after
applying the reduction rule is at most the claimed bound on T (N, K):
T (N 2, K 1) 1.5901N 2 8.109K1 0.3711 1.5901N 8.109K .
Reduction Rule 7 If w has no neighbours outside Z1 A2 , return NO from this
branch.
This can be justified as follows: for any solution A1 containing w, the set A1 \ w is
also a valid solution, and we are looking only for inclusion-minimal sets A1 .
Reduction Rule 8 If w has only a single neighbour w outside Z1 A2 , contract the
edge tw and proceed treating w as the new w.
The justification of this is that again, if w were not to be a part of the solution, we
could also remove w from the solution.
Reduction Rule 9 If w has more than one neighbour outside Z1 A2 , we branch. We
either decide w is a branching point (in which case we contract tw, reduce the limit
on the number of branching points by one, and return to the original problem), or that
it is not. In the latter case, exactly one of the neighbours of w is in the solutionthus
we branch on which one is it, contract the edge tw, put the remaining neighbours of
w in A2 and proceed treating the selected neighbour as the new w.
To check the complexity assumptions we verify that for any d 3 the running time
after applying the reduction rule is at most the claimed bound on T (N, K):
T (N 1, K 1) + (d 1)T (N (d 1), K)
1.5901N 1 8.109K1 + (d 1)0.3711 1.5901N (d1) 8.109K
0.3711 1.5901N 8.109K .
As d/(d 1) 1.5 < 1.5901 for d 3, the above inequality may be verified only
for d = 3.
Algorithmica (2014) 70:195207
203
3.2 Proof of Lemma 1
Lemma 2 (Lemma 1, Restated) Let H be any graph with at least 2 vertices. Let k be
the number of vertices of H that are not articulation points, and let l be the number
of articulation points of degree at least three. Then 3k 6 l.
Proof Let us denote m = 3k l, our goal is to prove that for any graph H we have
m 6. Let us assume the contrary: there exist graphs for which m < 6. Let H0 be the
one with minimum number of vertices, a minimal counterexample. We now examine
the structure of H0 in order to find a contradiction.
We first claim that H0 is connected. If H0 is edgeless, k 2, l = 0 and 3k l 6.
If H0 contains an isolated vertex v, H0 has at least three vertices, and by deleting
v we obtain a smaller counterexample, as we decrease k and keep the value of l.
Otherwise, we note that m is additive with respect to connected components, so in
case of disconnectedness one of its components would be a smaller counterexample
with at least two vertices.
Observe that H0 cannot have an articulation point of degree 2. In such a situation
we could contract one of the incident edges; this operation changes neither k nor l,
so m stays the same and we obtain a smaller counterexample.
Now assume that H0 contains an articulation point v, such that we can partition
the connected components of H0 [V \ {v}] into two parts with vertex sets V1 , V2 , for
which |V1 |, |V2 | > 1. Note that H0 [V1 {v}] and H0 [V2 {v}] are connected. As the
degree of v is at least 3, let us assume without losing generality that the degree of v
in H0 [V1 {v}] is at least 2. Consider two graphs:
H1 , being H0 [V1 {v}] with a pendant (a degree-1 vertex) attached to v;
H2 := H0 [V2 {v}].
Both H1 and H2 have less vertices than H0 , so if for i = 1, 2 we denote by ki , li the
numbers of non-articulation points and articulation points of degree at least 3 in Hi
respectively, then mi := 3ki li 6.
Observe that k k1 + k2 2, as every vertex from V \ {v} that was a nonarticulation point in a corresponding Hi is also a non-articulation point in H0 , while
v is an articulation point in H1 . Moreover, l l1 + l2 , as every articulation point of
degree at least 3 in H0 is also an articulation point of degree at least 3 in either H1
or H2 . Hence,
m = 3k l 3(k1 + k2 2) (l1 + l2 ) = m1 + m2 6 6,
a contradiction with H0 being a counterexample.
Take any articulation point v in H0 . As the partition described above is not possible, removing v from the graph results in H0 being split into exactly two connected
components: one of size |V (H )| 2 and one of size 1. Therefore, every articulation
point in H0 has a neighbour of degree 1, which obviously is not an articulation point.
Hence, l k and, consequently, 6 > 3k l 2k, which leads to l k 2. Now
observe that
204
Algorithmica (2014) 70:195207
if l = 0, then k 2 as H0 has at least two vertices, so m 6, a contradiction;
if l = 1, then the only articulation point must have at least three neighbours, so
k 3, a contradiction;
otherwise l = 2 and the graph is isomorphic to P4 , a contradiction as well.
In each case we obtained a contradiction, which finishes the proof.
Remark 1 One might wonder whether the constants obtained in the proof are optimal,
and whether we could strengthen the bound to achieve a better complexity of the
algorithm. In fact, this is not the case: there exists an infinite family of graphs with
unbounded k, l, for which the inequality from Lemma 1 is tight. An example of such
a graph is one constructed from a set of disjoint triangles by connecting them in a
tree-like manner by bridges, and by adding a degree-1 neighbours to some of the
vertices of the triangles, such that each vertex of the triangles has degree exactly
three.
4 The 2-D ISJOINT C ONNECTED S UBGRAPHS Problem Parameterized by the
Number of Non-terminals
In this section we consider the 2-D ISJOINT C ONNECTED S UBGRAPHS problem parameterized by the number of non-terminals and prove Theorems 2 and 3.
First we prove that the S ET S PLITTING problem parameterized by the size of
the universe does not admit a polynomial kernel unless NP coNP/poly (that is,
prove Theorem 4), which we later use for the kernelization hardness of 2-D ISJOINT
C ONNECTED S UBGRAPHS. As the starting point we use the following result of Dom
et al. [10].
C OLOUR H ITTING S ET
Input: A set system (F , U ), where F 2U , an integer k |U | and a colour function c : U {0, . . . , k 1}.
Task: Does there exists a subset X U , which contains at most one element of
each of the k colours, such that each set in F contains an element from X?
Theorem 6 [10] The C OLOUR H ITTING S ET problem parameterized by the size of
the universe does not have a polynomial kernel unless NP coNP/poly.
Lemma 3 There exists a polynomial time algorithm which given an instance I =
(F , U ) of C OLOUR H ITTING S ET creates an instance I = (F , U ) of S ET S PLITTING , where |U | = |U | + 2, such that I is a YES-instance iff I is a YES-instance.
Proof Let I = (F , U, k, c) be an instance of C OLOUR H ITTING S ET. We create the following instance I = (F , U ) of S ET S PLITTING. As the universe U
we take U = U {uin , uout }. As the family F we set F = {{uout } S : S
F } {{uin , uout }} {{uin , u1 , u2 } : u1 , u2 U u1 = u2 c(u1 ) = c(u2 )}. We want
to prove that I is a YES-instance of C OLOUR H ITTING S ET iff I is a YES-instance
of S ET S PLITTING.
Algorithmica (2014) 70:195207
205
First assume that I is a YES-instance of C OLOUR H ITTING S ET and let X U
be any solution. We claim that X = X {uin } is a solution to S ET S PLITTING. Obviously we split the set {uin , uout }. Since each set in F contains an element of X and
uout
/ X we infer that each set of {{uout } S : S F } is split by X . Finally, X
contains at most one element of each colour, therefore each set {uin , u1 , u2 } is split,
because uin X and at least one element of {u1 , u2 } belongs to U \ X .
Now let us assume that I is a YES-instance of S ET S PLITTING and let X U
be any solution. Since by symmetry U \ X is also a solution for I , and there
exists a set {uin , uout } in I , w.l.o.g. we assume that uin X and uout
/ X . Let
X = X \ {uin } U . We prove that X is a solution for the instance I . Since each
set in {{uout } S : S F } is split by X and uout
/ X we infer that X contains at
least one vertex from each set in F . Moreover, since each set of the form {uin , u1 , u2 }
is split and uin X , we know that X contains at most one element of each colour
and, consequently, I is a YES-instance.
Theorem 4 follows from pipelining Theorems 5 and 6 and Lemma 3. Note that
here we use the fact that C OLOUR H ITTING S ET is NP-hard and S ET S PLITTING is
in NP. Now we show a reduction from S ET S PLITTING to 2-D ISJOINT C ONNECTED
S UBGRAPHS.
Lemma 4 There exists a polynomial time algorithm which given an instance (F , U )
of S ET S PLITTING creates an instance (G = (V , E), Z1 , Z2 ) of 2-D ISJOINT C ON NECTED S UBGRAPHS , where |V | |Z1 | |Z2 | = |U |, such that (F , U ) is a YESinstance iff (G, Z1 , Z2 ) is a YES-instance.
Proof Let (F , U ) be an instance of the S ET S PLITTING problem. We construct the
following graph G = (V , E), where V = {z1 , z2 } U {v1S , v2S : S F }, that is as
the vertex set we take two special vertices z1 ,z2 , one vertex for each element of the
universe U and two vertices for each set of the family F . We define the set of edges
of the graph G as E = {z1 u, z2 u : u U } {v1S u, v2S u : S F u S}. Finally
we define Z1 = {z1 } {v1S : S F } and Z2 = {z2 } {v2S : S F }, hence the only
non-terminal vertices in G are vertices of U .
Now we prove that (F , U ) is a YES-instance of S ET S PLITTING iff (G =
(V , E), Z1 , Z2 ) is a YES-instance of 2-D ISJOINT C ONNECTED S UBGRAPHS. First
assume that X U is a solution for (F , U ). We set A1 = Z1 X and A2 =
Z2 (U \ X). Since each set in S F contains both an element of X and of U \ X, all
the vertices from A1 are connected to z1 and all the vertices from A2 are connected
to z2 . Therefore, the subgraphs G[A1 ] and G[A2 ] are connected and, consequently,
(G, Z1 , Z2 ) is a YES-instance.
In the other direction assume that (G = (V , E), Z1 , Z2 ) is a YES-instance and let
(A1 , A2 ) be a solution. We claim that X = A1 U is a solution to (F , U ). Indeed,
since both G[A1 ] and G[A2 ] are connected, we infer that each set S F contains
both an element of X and of U \ X; otherwise either vertices z1 , v1S or z2 , v2S would
be disconnected in G[A1 ] and G[A2 ] respectively.
Similarly as in the case of Theorem 4, also Theorem 3 follows from pipelining
Theorems 5 and 6 and Lemmas 3 and 4. Again, we use here the fact that C OLOUR
206
Algorithmica (2014) 70:195207
H ITTING S ET is NP-hard and 2-D ISJOINT C ONNECTED S UBGRAPHS is in NP. To
prove Theorem 2 we pipeline Lemma 4 with the following recent result:
Theorem 7 [9] There does not exist an epsilon > 0 and an algorithm running in
(2 )|U | (|U | + |F |)O(1) time for the S ET S PLITTING problem unless the Strong
Exponential Time Hypothesis is false.
Remark 2 The proof of Theorem 7 in [9] reduces a -CNF-SAT instance (for any )
to a S ET S PLITTING instance with a number of sets linear in the number of clauses
in the input. If we pipeline this reduction with Lemma 4, we obtain an instance with
much more terminals than non-terminals: k non-terminals yields roughly k terminals. Therefore there is much space for improvement between the instances produced
by this reduction and the ones where our O(1.933n )-time algorithm does not fall back
to the brute-force solution.
5 Conclusions
In this paper we studied the general case of 2-D ISJOINT C ONNECTED S UBGRAPHS
problem and showed an algorithm achieving running time O(1.933n ), thus breaking
the 2n barrier. For the natural parameterization by the number of non-terminals we
have shown a matching lower bound for the naive O(2k nO(1) ) upper bound. Moreover, the existence of a polynomial kernel is unlikely.
Recently, Telle and Villanger announced an even faster exact algorithm for the 2D ISJOINT C ONNECTED S UBGRAPHS problem, with running time O(1.7804n ) [20].
The work of Telle and Villanger uses a similar approach, and provides a deeper combinatorial study of the problem of connecting a set of terminals with a small number
of vertices, considered from the perspective of exact algorithms.
Acknowledgements Marek Cygan is partially supported by NCN grant N206567140, Foundation for
Polish Science, and ONR YIP grant no. N000141110662. Marcin Pilipczuk is partially supported by NCN
grant N206491038 and Foundation for Polish Science. Micha Pilipczuk is partially supported by the
European Research Council (ERC) grant Rigorous Theory of Preprocessing, reference 267959. Jakub
Onufry Wojtaszczyk is partially supported by NCN grant N206567140.
Open Access This article is distributed under the terms of the Creative Commons Attribution License
which permits any use, distribution, and reproduction in any medium, provided the original author(s) and
the source are credited.
References
1. Bjrklund, A.: Determinant sums for undirected Hamiltonicity. In: FOCS, pp. 173182. IEEE Comput. Soc., Los Alamitos (2010)
2. Bjrklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets Mbius: fast subset convolution.
In: Johnson, D.S., Feige, U. (eds.) STOC, pp. 6774. ACM, New York (2007)
3. Bjrklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput.
39(2), 546563 (2009)
Algorithmica (2014) 70:195207
207
4. Bodlaender, H.L., Thomass, S., Yeo, A.: Analysis of data reduction: transformations give evidence
for non-existence of polynomial kernels. Technical report UU-CS-2008-030, Institute of Information
and Computing Sciences, Utrecht University, Netherlands (2008)
5. Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In:
Chen, J., Fomin, F.V. (eds.) IWPEC. Lecture Notes in Computer Science, vol. 5917, pp. 7585.
Springer, Berlin (2009)
6. Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theor. Comput. Sci. 411(4042), 3701
3713 (2010)
7. Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving
connectivity problems parameterized by treewidth in single exponential time. In: Ostrovsky, R. (ed.)
FOCS, pp. 150159. IEEE Press, New York (2011)
8. Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Scheduling partially ordered jobs faster
than 2n . In: Demetrescu, C., Halldrsson, M.M. (eds.) ESA. Lecture Notes in Computer Science,
vol. 6942, pp. 299310. Springer, Berlin (2011)
9. Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S.,
Wahlstrm, M.: On problems as hard as CNF-SAT. In: IEEE Conference on Computational Complexity, pp. 7484. IEEE Press, New York (2012)
10. Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S.,
Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) ICALP (1). Lecture Notes
in Computer Science, vol. 5555, pp. 378389. Springer, Berlin (2009)
11. Fomin, F., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)
12. Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact
algorithms. J. ACM 56(5), 132 (2009)
13. Fomin, F.V., Todinca, I., Villanger, Y.: Exact algorithm for the maximum induced planar subgraph
problem. In: Demetrescu, C., Halldrsson, M.M. (eds.) ESA. Lecture Notes in Computer Science,
vol. 6942, pp. 287298. Springer, Berlin (2011)
14. Gray, C., Kammer, F., Lffler, M., Silveira, R.I.: Removing local extrema from imprecise terrains.
Comput. Geom. 45(7), 334349 (2012)
15. Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367375 (2001)
16. Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pp. 777789 (2011)
17. Patrascu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Charikar, M. (ed.) SODA,
pp. 10651075. SIAM, Philadelphia (2010)
18. Paulusma, D., van Rooij, J.M.M.: On partitioning a graph into two connected subgraphs. Theor. Comput. Sci. 412(48), 67616769 (2011)
19. Robertson, N., Seymour, P.D.: Graph minors XIII. The disjoint paths problem. J. Comb. Theory, Ser.
B 63(1), 65110 (1995)
20. Telle, J.A., Villanger, Y.: Connecting terminals and 2-disjoint connected subgraphs. (2013).
arXiv:1301.2506v1
21. van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer. In:
Fiat, A., Sanders, P. (eds.) ESA. Lecture Notes in Computer Science, vol. 5757, pp. 554565. Springer,
Berlin (2009)
22. van t Hof, P., Paulusma, D., Woeginger, G.J.: Partitioning graphs into connected parts. Theor. Comput. Sci. 410(4749), 48344843 (2009)
