Below all subsets for Minimal Connected Dominating Set∗

arXiv:1611.00840v1 [] 2 Nov 2016

Daniel Lokshtanov†

Michal Pilipczuk‡

Saket Saurabh§

Abstract
A vertex subset S in a graph G is a dominating set if every vertex not contained in S has a
neighbor in S. A dominating set S is a connected dominating set if the subgraph G[S] induced
by S is connected. A connected dominating set S is a minimal connected dominating set if no
proper subset of S is also a connected dominating set. We prove that there exists a constant
ǫ > 10−50 such that every graph G on n vertices has at most O(2(1−ǫ)n ) minimal connected
dominating sets. For the same ǫ we also give an algorithm with running time 2(1−ǫ)n · nO(1) to
enumerate all minimal connected dominating sets in an input graph G.

1

Introduction

In the field of enumeration algorithms, the following setting is commonly considered. Suppose we
have some universe U and some property Π of subsets of U . For instance, U can be the vertex set
of a graph G, whereas Π may be the property of being an independent set in G, or a dominating
set of G, etc. Let F be the family of all solutions: subsets of U satisfying Π. Then we would like to
find an algorithm that enumerates all solutions quickly, optimally in time |F| · nO(1) , where n is the
size of the universe. Such an enumeration algorithm could be then used as a subroutine for more
general problems. For instance, if one looks for an independent set of maximum possible weight is
a vertex-weighted graph, if suffices to browse through all inclusion-wise maximal independent sets
(disregarding the weights) and pick the one with the largest weight. If maximal independent sets
can be efficiently enumerated and their number turns out to be small, such an algorithm could be
useful in practice.
The other motivation for enumeration algorithms stems from extremal problems for graph properties. Suppose we would like to know what is, say, the maximum possible number of inclusion-wise
maximal independent sets in a graph on n vertices. Then it suffices to find an enumeration algorithm for maximal independent sets, and bound its (exponential) running time in terms of n. The
standard approach for the design of such an enumeration algorithm is to construct a smart branching procedure. The run of such a branching procedure can be viewed as a tree where the nodes
correspond to moments when the algorithm branches into two or more subprocedures, fixing different choices for the shape of a solution. Then the leaves of such a search tree correspond to the
discovered solutions. By devising smart branching rules one can limit the number of leaves of the
∗

The research of S. Saurabh leading to these results has received funding from the European Research Council
under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement no. 306992.
The research of Mi. Pilipczuk is supported by Polish National Science Centre grant UMO-2013/11/D/ST6/03073.
Mi. Pilipczuk is also supported by the Foundation for Polish Science via the START stipend programme.
†
Department of Informatics, University of Bergen, Norway, daniello@ii.uib.no.
‡
Institute of Informatics, University of Warsaw, Poland, michal.pilipczuk@mimuw.edu.pl.
§
Institute of Mathematical Sciences, India, saket@imsc.res.in, and Department of Informatics, University of
Bergen, Norway, Saket.Saurabh@ii.uib.no.

1

search tree, which both estimates the running time of the enumeration algorithm, and provides a
combinatorial upper bound on the number of solution. For instance, the classic proof of Moon and
Moser [9] that the number of maximal independent sets in an n-vertex graph is at most 3n/3 , can
be easily turned into an algorithm enumerating this family in time 3n/3 · nO(1) .
However, the analysis of branching algorithms is often quite nontrivial. The technique usually
used, called Measure&Conquer, involves assigning auxiliary potential measures to subinstances obtained during branching, and analyzing how the potentials change during performing the branching
rules. Perhaps the most well-known result obtained using Measure&Conquer is the O(1.7159n )-time
algorithm of Fomin et al. [4] for enumerating minimal dominating sets. Note that in particular this
implies an O(1.7159n ) upper bound on the number of minimal dominating sets. We refer to the
book of Fomin and Kratsch [5] for a broader discussion of branching algorithms and the Measure&Conquer technique.
The main limitation of such branching strategies is that, without any closer insight, they can
only handle properties that are somehow local. This is because pruning unnecessary branches is
usually done by analyzing specific local configurations in the graph. For this reason, it is difficult
to add requirements of global nature to the framework. To give an example, consider the family of
minimal connected dominating sets of a graph: a subset of vertices S is a minimal connected dominating set if it induces a connected subgraph, is a dominating set, and no its proper subset has both
these properties. While the number of minimal dominating sets of an n-vertex graph is bounded
by O(1.7159n ) by the result of Fomin et al. [4], for the number of minimal connected dominating
sets no upper bound of the form O(cn ) for any c < 2 was known prior to this work. The question
about the existence of such an upper bound was asked by Golovach et al. [6], and then re-iterated
by Kratsch [1] during the recent Lorentz workshop “Enumeration Algorithms using Structure”. We
remark that the problem of finding a minimum-size connected dominating set admits an algorithm
with running time O(1.9407n ) [3], but the method does not generalize to enumerating minimal
connected dominating sets.
Our results.

We resolve this question in affirmative by proving the following theorem.

Theorem 1. There is a constant ǫ > 10−50 such that every graph G on n vertices has at most
O(2(1−ǫ)n ) minimal connected dominating sets. Further, there is an algorithm that given as input
a graph G, lists all minimal connected dominating sets of G in time 2(1−ǫ)n · nO(1) .
Note that we give not only an improved combinatorial upper bound, but also a corresponding
enumeration algorithm. The improvement is minuscule, however our main motivation was just to
break the trivial 2n upper bound of enumerating all subsets. In many places our argumentation
could be improved to yield a slightly better bound at the cost of more involved analysis. We choose
not to do it, as we prefer to keep the reasoning as simple as possible, while the improvements would
not decrease our upper bound drastically anyway. The main purpose of this work is to show the
possibility of achieving an upper bound exponentially smaller than 2n , and thus to investigate what
tools could be useful for the treatment of requirements of global nature in the setting of extremal
problems for graph properties.
For the proof of Theorem 1, clearly it is sufficient to bound the number of minimal connected
dominating sets of size roughly n/2. The starting point is the realization that any vertex u in a
minimal connected dominating set S serves one of two possible roles. First, u can be essential for
domination, which means that there is some v not in S such that u is the only neighbor of v in S.
Second, u can be essential for connectivity, in the sense that after removing u, the subgraph induced
by S would become disconnected. Therefore, if we suppose that the vertices essential for domination
2

form a small fraction of S, we infer that almost every vertex of G[S] is a cut-vertex of this graph.
It is not hard to convince oneself that then almost every vertex of S has degree at most 2 in G[S].
All in all, regardless whether the number of vertices essential for domination is small or large,
a large fraction of all the vertices of the graph has at most 2 neighbors in S. Intuitively, in an
“ordinary” graph the number of sets S with this property should be significantly smaller than 2n .
We prove that this is indeed the case whenever the graph is “robustly dense” in the following sense:
it has a spanning subgraph where almost all vertices have degrees not smaller than some constant
ℓ, but no vertex has degree larger than some (much larger) constant h. For this proof we use the
probabilistic method: we show that if S is sampled at random, then the probability that many vertices are adjacent to at most 2 vertices of S is exponentially small. The main tool is Chernoff-like
concentration of independent random variables.
The remaining case is when the spanning subgraph as described above cannot be found. We
attempt at constructing it using a greedy procedure, which in case of failure discovers a different
structure in the graph. We next show that such a structure can be also used to design an algorithm
for enumerating minimal connected dominating sets faster than 2n , using a more direct branching
strategy. The multiple trade-offs made in this part of the proof are the main reason for why our
improvement over the trivial 2n upper bound is so small.

2

Preliminaries

All graphs considered in this paper are simple, i.e., they do not have self-loops or multiple edges
connecting the same pair of vertices. For a graph G, by V (G) and E(G) we denote the vertex and
edge sets of G, respectively. The neighborhood of a vertex v in a graph G is denoted by NG (v), and
consists of vertices adjacent to v. The degree of v, denoted by d(v), is defined the cardinality of its
neighborhood. For a subset S ⊆ V (G) and vertex v ∈ V (G) the S-degree of v, denoted dS (v), is
defined to be the number of vertices in S adjacent to v. A proper coloring of a graph G with c colors
is a function φ : V (G) → {1, . . . , c} such that for every edge uv ∈ E(G) we have φ(u) 6= φ(v). For a
proper coloring φ of G and integer i ≤ c, the i-th color class of φ is the set Vi = φ−1 (i). The subgraph
of G induced by a vertex subset S ⊆ V (G) is denoted by G[S] and defined to be the graph with
vertex set S and edge set {uv ∈ E(G) : u, v ∈ S}. For a vertex v ∈ V (G), the graph G − v is simply
G[V (G) \ {v}]. A subset I of vertices is independent if it induced an edgeless graph, that is, a graph
with no edges. A cutvertex in a connected graph G is a vertex v such that G − v is disconnected.
We denote exp(t) = et . The probability of an event A is denoted by Pr[A] and the expected
value of a random variable X is denoted by E[X]. We use standard concentration bounds for sums
of independent random variables. In particular, the following variant of the Hoeffding’s bound [8],
given by Grimmett and Stirzaker [7, p. 476], will be used.
Theorem 2 (Hoeffding’s bound). Suppose X1 , X2 , . . . , Xn are independent random variables such
that ai ≤ Xi ≤ bi for all i. Let X = Σni=1 Xi . Then:
!
−2t2
.
Pr[X − E[X] ≥ t] ≤ exp
Σni=1 (bi − ai )2
For enumeration, we need the following folklore claim.
Lemma 3. Let U be a universe of size n and let F ⊆ 2U be a family of its subsets that is closed
under taking subsets (X ⊆ Y and Y ∈ F implies X ∈ F), and given a set X it can be decided in
polynomial time whether X ∈ F. Then F can be enumerated in time |F| · nO(1) .
3

Proof. Order the elements of U arbitrarily as e1 , e2 , . . . , en , and process them in this order while
keeping some set X ∈ F, initially set to be the empty set. When considering the next ei , check if
X ∪ {ei } ∈ F. If this is not the case, just proceed further with X kept. Otherwise, output X ∪ {ei }
as the next discovered set from F, and execute two subprocedures: in the first proceed with X, and
in the second proceed with X ∪ {ei }. It can be easily seen that every set of F is discovered by the
procedure, and that some new set of F is always discovered within a polynomial number of steps (i.e.,
this is a polynomial-delay enumeration algorithm). Thus, the total running time is |F| · nO(1) .

3

Main case distinction

The first step in our proof is to try to find a spanning subgraph of the considered graph G, which
has constant maximum degree, but where only a small fraction of vertices have really small degrees.
This is done by performing a greedy construction procedure. Obviously, such a spanning subgraph
may not exist, but then we argue that the procedure uncovers some other structure in the graph,
which may be exploited by other means. The form of the output of the greedy procedure constitutes
the main case distinction in our proof.
Lemma 4. There is an algorithm that given as input a graph G, together with integers ℓ and h
such that 1 ≤ ℓ ≤ h, and a real δ with 0 ≤ δ ≤ 1, runs in polynomial time and outputs one of the
following two objects:
1. A subgraph G′ of G with V (G′ ) = V (G), such that
• every vertex in G′ has degree at most h, and
• less than δ · n vertices in G′ have degree less than ℓ.
2. A partition of V (G) into subsets L, H and R such that
• |L| ≥ δ · n,
• every vertex in L has strictly less than ℓ neighbors outside H, and
• |H| ≤

2ℓ
h

· n.

Proof. The algorithm takes as input ℓ, h and δ and computes a subgraph G′ of G as follows. Initially V (G′ ) = V (G) and E(G′ ) = ∅. As long as there is an edge uv ∈ E(G) \ E(G′ ) such that
(a) both u and v have degree strictly less than h in G′ , and (b) at least one of u and v has degree
strictly less than ℓ in G′ , the algorithm adds the edge uv to E(G′ ). When the algorithm terminates,
G′ is a subgraph of G with V (G′ ) = V (G), such that every vertex in G′ has degree at most h. Let
L be the set of vertices that have degree strictly less than ℓ in G′ . If |L| < δ · n then the algorithm
outputs G′ , as G′ satisfies the conditions of case 1.
Suppose now that |L| ≥ δ · n. Let H be the set of vertices of degree exactly h in G′ , and let
R be V (G) \ (L ∪ H). Clearly L, H, and R form a partition of V (G). Consider any vertex u ∈ L.
There can not exist an edge uv ∈ E(G) \ E(G′ ) with v ∈
/ H, since such an edge would be added to
′
E(G ) by the algorithm. Thus every vertex v ∈ NG (u) \ H is also a neighbor of u in G′ . Since the
degree of u in G′ is less than ℓ, we conclude that |NG (u) \ H| < ℓ.
′
Finally, we show that |H| ≤ 2ℓ
h · n. To that end, we first upper bound |E(G )|. Consider the
potential function
X
φ(G′ ) =
max(ℓ − dG′ (v), 0).
v∈V (G′ )

4

Initially the potential function has value nℓ. Each time an edge is added to G′ by the algorithm,
the potential function decreases by (at least) 1, because at least one endpoint of the added edge
has degree less than ℓ. Further, when the potential function is 0, there are no vertices of degree
less than ℓ, and so the algorithm terminates. Thus, the algorithm terminates after at most nℓ
iterations, yielding |E(G′ )| ≤ nℓ. Hence, the sum of the degrees of all vertices in G′ is at most 2nℓ.
Since every vertex in H has degree h, it follows that |H| ≤ 2ℓ
h · n.
1
To prove Theorem 1, we apply Lemma 4 with ℓ = 14, h = 3 · 105 and δ = 60
. There are two
′
′
possible outcomes. In the first case we obtain a subgraph G of G with V (G ) = V (G), such that
1
every vertex in G′ has degree at most 3 · 105 , and at most 60
· n vertices in G′ have degree less than
14. We handle this case using the following Lemma 5, proved in Section 4.

Lemma 5. Let G be a graph on n vertices that has a subgraph G′ with V (G′ ) = V (G) and the
1
· n vertices in G′
following properties: every vertex in G′ has degree at most 3 · 105 , and less than 60
−26
have degree less than 14. Then G has at most O(2n·(1−10 ) ) minimal connected dominating sets.
Further, there is an algorithm that given as input G and G′ , enumerates the family of all minimal
−26
connected dominating sets of G in time 2n·(1−10 ) · nO(1) .
1
In the second case we obtain a partition of V (G) into L, H, and R such that |L| ≥ 60
· n, every
3
vertex in L has strictly less than 14 neighbors outside H, and |H| ≤ 104 · n. This case is handled
by the following Lemma 6, which we prove in Section 5.

Lemma 6. Let G be a graph on n vertices that has a partition of V (G) into L, H and R such
1
· n, every vertex in L has strictly less than 14 neighbors outside H, and |H| ≤ 1014 · n.
that |L| ≥ 60
−50
Then G has at most 2n·(1−10 ) minimal connected dominating sets. Further, there is an algorithm
that given as input G together with the partition (L, H, R), enumerates the family of all minimal
−50
connected dominating sets of G in time 2n·(1−10 ) · nO(1) .
Together, Lemmas 5 and 6 complete the proof of Theorem 1.

4

Robustly dense graphs

In this section we bound the number of minimal connected dominating sets in a graph G that
satisfies case 1 of Lemma 4, that is, we prove Lemma 5. In particular, we assume that G has a
1
subgraph G′ such that all vertices of G′ have degree at most h = 3 · 105 , and less than δn = 60
n
vertices of G′ have degree less than ℓ = 14. For a set S, we say that a vertex v has low S-degree if
dS (v) ≤ 2. We define the set L(S) = {v ∈ V (G) : dS (v) ≤ 2} to be the set of vertices in G of low
S-degree. Our bound consists of two main parts. In the first part we give an upper bound on the
1
· n. In the second part we show that for any minimal
number of sets S in G such that |L(S)| ≥ 20
4
1
connected dominating set S of G of size at least 10
n, we have |L(S)| ≥ 20
·n. Together the two parts
immediately yield an upper bound on the number of (and an enumeration algorithm for) minimal
connected dominating sets in G. We begin by proving the first part using a probabilistic argument.
1
·n
Lemma 7. Let H be a graph on n vertices of maximum degree at most h, such that at most 60
n
−
2
n
4
vertices have degree less than ℓ ≥ 14. Then there are at most h · 2 · e 1800h subsets S of V (H)
1
· n.
such that |L(S)| ≥ 20

Proof. To prove the lemma, it is sufficient to show that if S ⊆ V (H) is selected uniformly at
1
· n is upper bounded as follows.
random, then the probability that |L(S)| is at least 20
5





1
n 
Pr |L(S)| >
· n ≤ h2 · exp −
20
1800h4

(1)

Let H 2 be the graph constructed from H by adding an edge between every pair of vertices in
H that share a common neighbor. Since H has maximum degree at most h, H 2 has maximum
degree at most h(h − 1) ≤ h2 − 1, and therefore H 2 can be properly colored with h2 colors [2].
Let φ : V (H) → {1, . . . , h2 } be a proper coloring of H 2 , and let V1 , V2 , . . . , Vh2 be the color classes
of φ. Two vertices in the same color class of φ have empty intersection of neighborhoods in H.
Thus, when S ⊆ V (H) is picked at random, we have that dS (u) and dS (v) are independent random
variables whenever u and v are in the same color class of φ.
1
) · n by
Let Q be the set of vertices in G of degree at least ℓ. We have that |Q| ≥ (1 − 60
Q
2
assumption. For each i ≤ h we set Vi = Vi ∩ Q. Next we upper bound, for each i ≤ h2 , the
1
probability that |L(S) ∩ ViQ | > 40h
2 · n. For every vertex v ∈ V (H), define the indicator variable
Xv which is set to 1 if dS (v) ≤ 2 and Xv is set to 0 otherwise. We have that


d(v)
+ d(v)
+ d(v)
0
1
2
.
Pr[Xv = 1] =
2d(v)
The right hand side is non-increasing with increasing d(v), so since we assumed d(v) ≥ ℓ, we have
2
(ℓ)+(ℓ)+( ℓ)
that Pr[Xv = 1] ≤ 0 21ℓ 2 ≤ 2ℓ ℓ . In particular this holds for every v ∈ Q. Thus, for every
P
i ≤ h2 we have that |L(S) ∩ ViQ | = v∈V Q Xv — that is, |L(S) ∩ ViQ | is a sum of |ViQ | independent
i

indicator variables, each taking value 1 with probability at most
(Theorem 2) yields

ℓ2
.
2ℓ

Thus, Hoeffding’s inequality

!


2
2
ℓ
n
2n
n 
Pr |L(S) ∩ ViQ | ≥ ℓ · |ViQ | +
≤
exp
−
.
≤
exp
−
2
60h2
1800h4
3600h4 |ViQ |


(2)

The union bound over the h2 color classes of φ, coupled with equation (2), yields that



ℓ2
1
n 
Pr |L(S) ∩ Q| ≥ ℓ |Q| +
· n ≤ h2 · exp −
.
2
60
1800h4

n
we have that
Hence, with probability at least 1 − h2 · exp − 1800h
4
|L(S) ∩ Q| ≤

ℓ2
2
1
·n≤
· n,
|Q| +
ℓ
2
60
60

where the last inequality holds due to ℓ ≥ 14. Since |L(S)| ≤ |L(S) ∩ Q| + |V (H) \ Q| and
1
1
n it follows that in this case, |L(S)| ≤ 20
· n. This proves equation (1) and the
|V (H) \ Q| ≤ 60
statement of the Lemma.
Note that the statement of Lemma 7 requires H to have at maximum degree at most h, such
1
· n vertices have degree less than ℓ. What we obtain from Lemma 4 is a subgraph
that at most 60
′
G of the input graph G with these properties. We will apply Lemma 7 to H = G′ and transfer the
conclusion to G, since G′ is a subgraph of G.
We now turn to proving the second part, that for any minimal connected dominating set S of
1
4
n, we have |L(S)| ≥ 20
· n. The first step of the proof is to show that any graph
G of size at least 10
where almost every vertex is a cut vertex must have many vertices of degree 2.
6

Lemma 8. Let α > 0 be a constant. Suppose that H is a connected graph on n vertices in which at
least (1 − α)n vertices are cutvertices. Then at least (1 − 7α)n vertices of H have degree equal to 2.
Proof. Let X be the set of those vertices of H that are not cutvertices. By the assumption we have
|X| ≤ αn. Let T be any spanning tree in H, and let L1 be the set of leaves of T . No leaf of T is a
cutvertex of H, hence L1 ⊆ X. Let L3 be the set of those vertices of T that have degree at least 3
in T . It is well-known that in any tree, the number of vertices of degree at least 3 is smaller than
the number of leaves. Therefore, we have the following:
|L3 | < |L1 | ≤ |X| ≤ αn.

(3)

Let R be the closed neighborhood of L1 ∪L3 ∪X in T , that is, the set consisting of L1 ∪L3 ∪X and
all vertices that have neighbors in L1 ∪ L3 ∪ X. Since T is a tree, it can be decomposed into a set of
paths P, where each path connects two vertices of L1 ∪ L3 and all its internal vertices have degree 2
in T . Contracting each of these paths into a single edge yields a tree on the vertex set L1 ∪L3 , which
means that the number of the paths in P is less than |L1 ∪ L3 |. Note that the closed neighborhood
of L1 ∪ L3 in T contains at most 2 of the internal vertices on each of the paths from P: the first
and the last one. Moreover, each vertex of X \ (L1 ∪ L3 ) introduces at most 3 vertices to R: itself,
plus two its neighbors on the path from P on which it lies. Consequently, by equation (3) we have:
|R| ≤ |L1 | + |L3 | + 2|L1 ∪ L3 | + 3|X| ≤ 7αn.

(4)

We now claim that every vertex u that does not belong to R, in fact has degree 2 in H. By the
definition of R we have that u has degree 2 in T , both its neighbors v1 and v2 in T also have degree 2
in T , and moreover u, v1 , and v2 are all cutvertices in H. Aiming towards a contradiction, suppose
u has some other neighbor w in H, different than v1 and v2 . Then the unique path from u to w in
T passes either through v1 or through v2 ; say, through v1 . However, then the removal of v1 from
H would not result in disconnecting H. This is because the removal of v1 from T breaks T into 2
connected components, as the degree of v1 in T is equal to 2, and these connected components are
adjacent in H due to the existence of the edge uw. This is a contradiction with the assumption
that v1 and v2 are cutvertices.
From equation (4) and the claim proved above it follows that at least (1 − 7α)n vertices of G
have degree equal to 2.
We now apply Lemma 8 to subgraphs induced by minimal connected dominating sets.
Lemma 9. Let S be a minimal connected dominating set of a graph G on n vertices, such that
4
1
|S| ≥ 10
n. Then |L(S)| ≥ 20
n.
Proof. For n ≤ 2 the claim is trivial, so assume n ≥ 3, which in particular implies |S| ≥ 2. Aiming
1
n. By minimality, we have that for every vertex v,
towards a contradiction, suppose |L(S)| < 20
the set S \ {v} is not a connected dominating set of G. Let
Scut = {v ∈ S : G[S] − v is disconnected}.
Consider a vertex v in S \ Scut . We have that S \ {v} can not dominate all of V (G) because
otherwise S \ {v} would be a connected dominating set. Let u be a vertex in of G not dominated
by S \ {v}. Because G[S] is connected and |S| ≥ 2, vertex v has a neighbor in S, so in particular
u 6= v and hence u ∈
/ S. Further, since S is a connected dominating set, u has a neighbor in S,
and this neighbor can only be v. Hence dS (u) = 1 and so u ∈ L(S). Re-applying this argument for
every v ∈ S \ Scut yields |L(S)| ≥ |S \ Scut |.
7

1
1
n, it follows that |S \ Scut | ≤ 20
n.
From the argument above and the assumption |L(S) < 20
4
1
1
Since |S| ≥ 10 n, we have that |S \ Scut | ≤ 8 |S|. It follows that |Scut | ≥ 8 |S|. By Lemma 8 applied
1
n. Each of these
to G[S], the number of degree 2 vertices in G[S] is at least (1 − 78 )|S| = 81 |S| ≥ 20
vertices belongs to L(S), which yields the desired contradiction.

We are now in position to wrap up the first case, giving a proof of Lemma 5.
P⌊ 4n
1
⌋ n
n(1− 100
)
4
10
Proof of Lemma 5. There are at most i=0
subsets of V (G) of size at most 10
· n.
i ≤2
4
Thus, the family of all minimal connected dominating sets of size at most 10 · n can be enumerated
1
4
in time 2n(1− 100 ) · nO(1) by enumerating all sets of size at most 10
· n, and checking for each set in
polynomial time whether it is a minimal connected dominating set.
4
Consider now any minimal connected dominating set S in G with |S| ≥ 10
· n. By Lemma 9,
1
we have that |L(S)| ≥ 20 n. Since every vertex of degree at most 2 in G has degree at most 2 in
1
n holds also in G′ . However, by Lemma 7 applied to G′ , there are
G′ , it follows that |L(S)| ≥ 20
n
1
at most 2n · e− 1800h4 subsets S of V (G′ ) = V (G) such that |L(S)| ≥ 20
· n (in G′ ). Substituting
−26
h = 3 · 105 in the above upper bound yields that there are at most 2n·(1−10 ) minimal connected
4
n, yielding the claimed upper bound on the number of minimal
dominating sets of size at least 10
connected dominating sets.
−26
4
n in time 2n·(1−10 ) ·
To enumerate all minimal connected dominating sets of G of size at least 10
1
nO(1) , it is sufficient to list all sets S such that |L(S)| ≥ 20
· n, and for each such set determine in
polynomial time whether it is a minimal connected dominating set. Note that the family of sets S
1
1
1
· n is closed under subsets: if |L(S)| ≥ 20
· n and S ′ ⊆ S then |L(S ′ )| ≥ 20
· n.
such that |L(S)| ≥ 20
1
Since it can be tested in polynomial time for a set S whether |L(S)| ≥ 20 · n, the family of all sets
−26
with |L(S)| ≥ 1 · n can be enumerated in time 2n·(1−10 ) nO(1) by the algorithm of Lemma 3,
20

completing the proof.

5

Large sparse induced subgraph

In this section we bound the number of minimal connected dominating sets in any graph G for
which case 2 of Lemma 4 occurs, i.e., we prove Lemma 6. Let us fix some integer ℓ ≥ 1.
Our enumeration algorithm will make decisions that some vertices are in the constructed connected dominating set, and some are not. We incorporate such decisions in the notion of extensions.
For disjoint vertex sets I and O (for in and out), we define an (I, O)-extension to be a vertex set
S that is disjoint from I ∪ O and such that I ∪ S is a connected dominating set in G. An (I, O)extension S is said to be minimal if no proper subset of it is also an (I, O)-extension. The following
simple fact will be useful.
Lemma 10. There is a polynomial-time algorithm that, given a graph G and disjoint vertex subsets
I, O, and S, determines whether S is a minimal (I, O)-extension in G.
Proof. The algorithm checks whether I ∪ S is a connected dominating set in G and returns “no”
if not. Then, for each v ∈ S the algorithm tests whether I ∪ (S \ {v}) is a connected dominating
set of G. If it is a connected dominating set for any choice of v, the algorithm returns “no”. Otherwise, the algorithm returns that S is a minimal (I, O)-extension. The algorithm clearly runs in
polynomial time, and if the algorithm returns that S is not a minimal (I, O)-extension in G, then
this is correct, as the algorithm also provides a certificate.
We now prove that if S is not a minimal (I, O) extension in G, then the algorithm returns
“no”. If S is not an (I, O)-extension at all, the algorithm detects it and reports no. If it is an
8

(I, O)-extension, but not a minimal one, then there exists an (I, O)-extension S ′ ( S. Let v be any
vertex in S \ S ′ . We claim that X = I ∪ (S \ {v}) is a connected dominating set of G. Indeed, X
dominates V (G) because I ∪S ′ does. Furthermore, G[X] is connected because G[I ∪S ′ ] is connected
and every vertex in X \ (I ∪ S ′ ) has a neighbor in (I ∪ S ′ ). Hence I ∪ (S \ {v}) is a connected
dominating set of G and the algorithm correctly reports “no”. This concludes the proof.
Observe that for any minimal connected dominating set X, and any I ⊆ X and O disjoint
from X, we have that X \ I is a minimal (I, O)-extension. Thus one can use an upper bound on
the number of minimal extensions to upper bound the number of minimal connected dominating
sets. Recall that case 2 of Lemma 4 provides us with a partition (L, H, R) of the vertex set. To
upper bound the number of minimal connected dominating sets, we will consider each of the 2n−|L|
possible partitions of H ∪ R into two sets I and O, and upper bound the number of minimal
(I, O)-extensions. This is expressed in the following lemma.
Lemma 11. Let G be a graph and (L, H, R) be a partition of the vertex set of G such that
|L| ≥ 10|H|ℓ, and every vertex in L has less than ℓ neighbors in L ∪ R. Then, for every parti−

tion (I, O) of H ∪ R, there are at most 2|L| · e

|L|
2−10ℓ ·100ℓ3

all minimal (I, O)-extensions can be listed in time

2|L|

minimal (I, O)-extensions. Furthermore,
−

·e

|L|
210ℓ ·100ℓ3

· nO(1) .

We now prepare ground for the proof of Lemma 11. The first step is to reduce the problem
essentially to the case when L is independent. For this, we shall say that a partition of V (G) into
L, H, and R is a good partition if:
• |L| ≥ 10|H|,
• L is an independent set, and
• every vertex in L has less than ℓ neighbors in R.
Towards proving Lemma 11, we first prove the statement assuming that the input partition of V (G)
is a good partition.
Lemma 12. Let G be a graph and (L, H, R) be a good partition of V (G). Then, for every partition
−

(I, O) of H ∪ R, there are at most 2|L| · e

|L|
210ℓ ·100ℓ2

minimal (I, O)-extensions. Furthermore, all
−

minimal (I, O)-extensions can be listed in time 2|L| · e

|L|
210ℓ ·100ℓ2

· nO(1) .

We will prove Lemma 12 towards the end of this section, now let us first prove Lemma 11
assuming the correctness of Lemma 12.
Proof of Lemma 11 assuming Lemma 12. Observe that we may find an independent set L′ in G[L]
of size at least |L|
ℓ . Indeed, since every vertex of L has less than ℓ neighbors in L ∪ R, any inclusion|L|
′
wise maximal independent set L′ in G[L] has size at least |L|
ℓ . Therefore |L | ≥ ℓ ≥ 10|H|, and
hence L′ , H, R′ = R ∪ (L′ \ L) is a good partition of V (G).
′
Further, for a fixed partition of R ∪ H into I and O, consider each of the 2|L\L | partitions of
H ∪ R′ into I ′ and O′ such that I ⊆ I ′ and O ⊆ O ′ . For every minimal (I, O)-extension S, we have
that S ∩ L′ is a minimal (I ′ , O′ )-extension, where I ′ = I ∪ (S \ L′ ) and O ′ = O ∪ (L \ (L′ ∪ S)).
Thus, by Lemma 12 applied to the good partition (L′ , H, R′ ) of V (G), and the partition (I ′ , O ′ ) of
H ∪ R′ , we have that the number of minimal (I, O)-extensions is upper bounded by
|L\L′ |

2

|L′ |

·2

−

·e

|L′ |
210ℓ 100ℓ2

9

−

≤ 2|L| · e

|L|
210ℓ 100ℓ3

.

Further, by the same argument, the minimal (I, O)-extensions can be enumerated within the
claimed running time, using the enumeration provided by Lemma 12 as a subroutine.
The next step of the proof of Lemma 12 is to make a further reduction, this time to the case
when also H ∪ R is independent. Since the partition into vertices taken and excluded from the
constructed connected dominating set is already fixed on H ∪ R, this amounts to standard cleaning
operations within H ∪ R. We shall say that a good partition (L, H, R) of V (G) is an excellent
partition if G[H ∪ R] is edgeless.
Lemma 13. There exists an algorithm that given as input a graph G, together with a good partition
(L, R, H) of V (G), and a partition (I, O) of R ∪ H, runs in polynomial time, and outputs a graph
G′ with V (G) ∩ V (G′ ) ⊇ L, an excellent partition (L, R′ , H ′ ) of V (G′ ), and a partition (I ′ , O′ ) of
R′ ∪ H ′ , with the following property. For every set S ⊆ L, S is a minimal (I, O)-extension in G if
and only if S is a minimal (I ′ , O ′ )-extension in G′ .
Proof. The algorithm begins by setting G′ = G, H ′ = H, R′ = R, I ′ = I and O′ = O. It then
proceeds to modify G′ , at each step maintaining the following invariants: (i) (L, H ′ , R′ ) is a good
partition of the vertex set of G′ , and (ii) for every set S ⊆ L, S is a minimal (I, O)-extension in G
if and only if S is a minimal (I ′ , O ′ )-extension in G′ .
If there exists an edge uv with u ∈ O′ and v ∈ I ′ , the algorithm removes u from G′ , from O′ , and
from R′ or H ′ depending on which of the two sets it belongs to. Since u is anyway dominated by I ′
and removing u can only decrease |H ′ | (while keeping |L| the same), the invariants are maintained.
If there exists an edge uv with both u and v in O′ , the algorithm removes the edge uv from G′ .
Since neither u nor v are part of I ′ ∪ S for any S ⊆ L, it follows that the invariants are preserved.
Finally, if there exists an edge uv with both u and v in I ′ , the algorithm contracts the edge uv.
Let w be the vertex resulting from the contraction. The algorithm removes u and v from I ′ and
from R′ or H ′ , depending on which of the two sets the vertices are in, and adds w to I ′ . If at least
one of u and v was in H ′ , w is put into H ′ , otherwise w is put into R′ . Note that |H ′ | may decrease,
but can not increase in such a step. Thus (L, R′ , H ′ ) remains a good partition and invariant (i) is
preserved. Further, since u and v are always in the same connected component of G′ [I ′ ∪ S] for any
S ⊆ L, invariant (ii) is preserved as well.
The algorithm proceeds performing one of the three steps above as long as there exists at least
one edge in G′ [R′ ∪ H ′ ]. When the algorithm terminates no such edge exists, thus (L, H ′ , R′ ) forms
an excellent partition of V (G′ ).
Lemma 13 essentially allows us to assume in the proof of Lemma 12 that (L, H, R) is an excellent partition of V (G). To complete the proof, we distinguish between two subcases: either there
|L|
are at most |L|
10 vertices in R of degree less than 10ℓ, or there are more than 10 such vertices. Let
us shortly explain the intuition behind this case distinction. If there are at most |L|
10 vertices in R of
degree less than 10ℓ, then it is possible to show that H ∪R is small compared to L, in particular that
minimal (I, O)-extension can not pick more than |H ∪ R|
|H ∪ R| ≤ 3|L|
10 . We then show that any
|L| 
vertices from L. This gives a 0.3|L| upper bound for the number of minimal (I, O)-extensions,

which is significantly lower than 2|L| .
On the other hand, if there are more than |L|
10 vertices in R of degree less than 10ℓ, then one can
find a large subset R′ of R of vertices of degree at most 10ℓ, such that no two vertices in R′ have a
common neighbor. For each vertex v ∈ R′ , every minimal (I, O)-extension must contain at least one
neighbor of v. Thus, there are only 2d(v) − 1, rather than 2d(v) possibilities for how a minimal (I, O)extension intersects the neighborhood of v. Since all vertices in R′ have disjoint neighborhoods,
 10ℓ |R′ |
on the number of minimal (I, O)-extensions.
this gives an upper bound of 2|L| · 2 210ℓ−1
10

We now give a formal treatment of the two cases. We begin with the case that there are at
most |L|
10 vertices in R of degree less than 10ℓ.
Lemma 14. Let G be a graph, and I and O be disjoint vertex sets such that I is nonempty and both
G[I ∪ O] and G− (I ∪ O) are edgeless. Then every minimal (I, O)-extension S satisfies |S| ≤ |I ∪ O|.
Proof of Lemma 14. We will need the following simple observation about the maximum size of an
independent set of internal nodes in a tree.
Claim 1. Let T be a tree and S be a set of non-leaf nodes of T such that S is independent in T .
Then |S| ≤ |V (T ) \ S|.
Proof. Root the tree T at an arbitrary vertex. Construct a vertex set Z by picking, for every s ∈ S,
any child z of s and inserting z into Z; this is possible since no vertex of S is a leaf. Every vertex
in T has a unique parent, so no vertex is inserted into Z twice, and hence |Z| = |S|. Further, since
S is independent, Z ⊆ V (T ) \ S. The claim follows.
y
We proceed with the proof of the lemma. Let X = V (G) \ (I ∪ O) and let S ⊆ X be a minimal
(I, O)-extension. Since I ∪ S is a connected dominating set and I ∪ O is independent, it follows
that every vertex in O has a neighbor in S. Hence G[I ∪ S ∪ O] is connected. Let T be a spanning
tree of G[I ∪ S ∪ O]. We claim that every node in S is a non-leaf node of T . Suppose not, then
G[I ∪ S \ {v}] is connected, every vertex in O has a neighbor in S \ {v}, v has a neighbor in I (since
G[I ∪ S] is connected and I is nonempty), and every vertex in X \ S has a neighbor in I. Hence
S \ {v} would be an (I, O)-extension, contradicting the minimality of S. We conclude that every
node in S is a non-leaf node of T . Applying Claim 1 to S in T concludes the proof.
The next lemma resolves the first subcase, when there are at most |L|
10 vertices in R of degree
less than 10ℓ. The crucial observation is that in this case, a minimal (I, O)-extension S must be of
size significantly smaller than |L|/2, due to Lemma 14.
Lemma 15. Let G be a graph, (L, H, R) be an excellent partition of V (G), and (I, O) be a partition of H ∪ R. If at most |L|
10 vertices in R have degree less than 10ℓ in G, then there are at most
|L|

2|L| · 2− 10 minimal (I, O)-extensions. Further, the family of all minimal (I, O)-extensions can be
|L|

enumerated in time 2|L| · 2− 10 · nO(1) .
Proof. First, note that |H| ≤ |L|
10 , because (L, H, R) is an excellent partition. Partition R into Rbig
and Rsmall according to the degrees: Rbig contains all vertices in R of degree at least 10ℓ, while
Rsmall contains the vertices in R of degree less than 10ℓ. Since every vertex in L has at most ℓ neigh|L|
3|L|
bors in R, it follows that |Rbig | ≤ |L|
10 . By assumption |Rsmall | ≤ 10 . It follows that |R ∪ H| ≤ 10 .
Now, I ∪ O = R ∪ H, and therefore, by Lemma 14 every minimal (I, O)-extension has size at most
|I ∪ O| ≤ 3|L|
10 . Hence the number of different minimal (I, O)-extensions is at most
3|L|
⌋

10
X
|L|

⌊

i=0

i

|L|

≤ 20.882|L| ≤ 2|L| · 2− 10 .

To enumerate the sets within the given time bound it is sufficient to go through all subsets S of
L of size at most 3|L|
10 and check whether S is a minimal (I, O)-extension in polynomial time using
the algorithm of Lemma 10.
We are left with the case when at least

|L|
10

vertices in R have degree less than 10ℓ in G.
11

Lemma 16. Let G be a graph, (L, H, R) be an excellent partition of V (G), and (I, O) be a partition of H ∪ R. If at least |L|
10 vertices in R have degree less than 10ℓ in G, then there are at
−

most 2|L| · e

|L|
210ℓ ·100ℓ2

minimal (I, O)-extensions. The family of all minimal (I, O)-extensions can
−

be enumerated in time 2|L| · e

|L|
210ℓ ·100ℓ2

· nO(1) .

Proof. We assume that |I ∪ O| ≥ 2, since otherwise the claim holds trivially. Let Rsmall be the set
of vertices in R of degree less than 10ℓ; by assumption we have |Rsmall | ≥ |L|
10 . Recall that vertices
in R have only neighbors in L, and every vertex of L has less than ℓ neighbors in R. Hence, for
each vertex r in Rsmall there are at most 10ℓ · (ℓ − 1) other vertices in Rsmall that share a common
neighbor with r. Compute a subset R′ of Rsmall as follows. Initially R′ is empty and all vertices in
Rsmall are unmarked. As long as there is an unmarked vertex r ∈ Rsmall , add r to R′ and mark r ′
as well as all vertices in Rsmall that share a common neighbor with r. Terminate when all vertices
in Rsmall are marked.
Clearly, no two vertices in the set R′ output by the procedure described above can share any
common neighbors. Further, for each vertex added to R′ , at most 10ℓ · (ℓ − 1) + 1 ≤ 10ℓ2 vertices
|L|
small |
≥ 100ℓ
are marked. Hence, |R′ | ≥ |R10ℓ
2
2.
Observe that if a subset S of L is an (I, O)-extension, then every vertex in I ∪ O must have a
neighbor in S. This holds for every vertex in O, because I ∪ S needs to dominate this vertex, but
there are no edges between O and I. For every vertex in I this holds because G[I ∪ S] has to be
connected, and I ∪ O is an independent set of size at least 2.
Consider now a subset S of L picked uniformly at random. We upper bound the probability
that every vertex in I ∪O has a neighbor in S. This probability is upper bounded by the probability
that every vertex in R′ has a neighbor in S. For each vertex r in R′ , the probability that none of
its neighbors is in S is 2−d(r) ≥ 2−10ℓ . Since no two vertices in R′ share a common neighbor, the
events “r has a neighbor in S” for r ∈ R′ are independent. Therefore, the probability that every
vertex in R′ has a neighbor in S is upper bounded by
′

−10ℓ · |L|
100ℓ2

(1 − 2−10ℓ )|R | ≤ e−2

−

=e

|L|
210ℓ ·100ℓ2

.

The upper bound on the number of minimal (I, O)-extensions follows. To enumerate all the minimal (I, O)-extensions within the claimed time bound, it is sufficient to enumerate all sets S ⊆ L
such that every vertex in R′ has at least one neighbor in S, and check in polynomial time using
Lemma 10 whether S is a minimal (I, O)-extension. The family of such subsets of L is closed under
taking supersets, so to enumerate them we can use the algorithm of Lemma 3 applied to their
complements.
We can now wrap up the proof of Lemma 12.
Proof of Lemma 12. Let G be a graph and (L, H, R) be a good partition of V (G). Consider a
partition of H ∪ R into two sets I and O. By Lemma 13, we can obtain in polynomial time a graph
G′ with V (G) ∩ V (G′ ) ⊇ L, as well as an excellent partition (L, R′ , H ′ ) of V (G′ ), and a partition
(I ′ , O′ ) of R′ ∪ H ′ , such that every subset S of L is a minimal (I, O)-extension in G if and only if it
is a minimal (I ′ , O ′ )-extension in G′ . Thus, from now on, we may assume without loss of generality
that L, H and R is an excellent partition of V (G).
We distinguish between two cases: either there are at most |L|
10 vertices in R of degree less than
|L|
10ℓ, or there are more than 10 such vertices. In the first case, by Lemma 15, there are at most
|L|

2|L| ·2− 10 minimal (I, O)-extensions. Further, the family of all minimal (I, O)-extensions can be enu|L|

−

merated in time 2|L| ·2− 10 ·nO(1) . In the second case, by Lemma 16, there are at most 2|L| ·e
12

|L|
210ℓ ·100ℓ2

minimal (I, O)-extensions, and the family of all minimal (I, O)-extensions can be enumerated in
−

time 2|L| · e

|L|
210ℓ ·100ℓ2

−

· nO(1) . Since e

|L|
210ℓ ·100ℓ2

|L|

≥ 2− 10 , the statement of the lemma follows.

As argued before, establishing Lemma 12 concludes the proof of Lemma 11. We can now use
Lemma 11 to complete the proof of Lemma 6, and hence also of our main result.
Proof of Lemma 6. To list all minimal connected dominating sets of G it is sufficient to iterate over
each of the 2n−|L| partitions of H ∪ R into I and O, for each such partition enumerate all minimal
(I, O)-extensions S using Lemma 11 with ℓ = 14, and for each minimal extension S check whether
I ∪ S is a minimal connected dominating set of G. Observe that
|L| ≥

1
1
· n ≥ 10 · 14 · 4 · n ≥ 10 · 14 · |H|,
60
10

and that therefore Lemma 11 is indeed applicable with ℓ = 14. Hence, the total number of minimal
connected dominating sets in G is upper bounded by
−

2n−|L| · 2|L| · e

|L|
210ℓ 100ℓ3

−

≤ 2n · 2

n
60·210ℓ 100ℓ3

−50 )

≤ 2n(1−10

.

The running time bound for the enumeration algorithm follows from the running time bound of
the enumeration algorithm of Lemma 11 in exactly the same way.
Acknowledgements. The authors gratefully thank the organizers of the workshop Enumeration Algorithms Using Structure, held in Lorentz Center in Leiden in August 2015, where this work
was initiated.

References
[1] Hans L. Bodlaender, Endre Boros, Pinar Heggernes, and Dieter Kratsch. Open problems of the Lorentz
workshop “Enumeration Algorithms using Structure”, 2015. Utrecht University Technical Report
UU-CS-2015-016. URL: http://www.cs.uu.nl/research/techreps/repo/CS-2015/2015-016.pdf.
[2] Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer,
2012.
[3] Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. Solving Connected Dominating Set faster than
2n . Algorithmica, 52(2):153–166, 2008.
[4] Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, and Alexey A. Stepanov. Combinatorial bounds
via measure and conquer: Bounding minimal dominating sets and applications. ACM Trans. Algorithms,
5(1), 2008.
[5] Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer
Science. An EATCS Series. Springer, 2010.
[6] Petr A. Golovach, Pinar Heggernes, and Dieter Kratsch. Enumerating minimal connected dominating
sets in graphs of bounded chordality. Theor. Comput. Sci., 630:63–75, 2016.
[7] Geoffrey Grimmett and David Stirzaker. Probability and random processes. Oxford university press, 2001.
[8] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the
American statistical association, 58(301):13–30, 1963.
[9] John W. Moon and Leo Moser. On cliques in graphs. Israel Journal of Mathematics, 3:23–28, 1965.

13

