arXiv:1510.07188v1 [] 24 Oct 2015

On the Dominating Set Problem in Random
Graphs
Yinglei Song
School of Electronics and Information Science
Jiangsu University of Science and Technology
Zhenjiang, Jiangsu 212003, China
syinglei2013@163.com
Abstract
In this paper, we study the Dominating Set problem in random graphs. In a random graph,
each pair of vertices are joined by an edge with a probability of p, where p is a positive constant
less than 1. We show that, given a random graph in n vertices, a minimum dominating set in
2
the graph can be computed in expected 2O(log2 n) time. For the parameterized dominating set
problem, we show that it cannot be solved in expected O(f (k)nc ) time unless the minimum
dominating set problem can be approximated within a ratio of o(log2 n) in expected polynomial
time, where f (k) is a function of the parameter k and c is a constant independent of n and k.
In addition, we show that the parameterized dominating set problem can be solved in expected
1
O(f (k)nc ) time when the probability p depends on n and equals to g(n)
, where g(n) < n is
a monotonously increasing function of n and its value approaches infinity when n approaches
infinity.

Keywords: dominating set, random graphs, expected computation time, parameterized computation

1

Introduction

Given a graph G = (V, E), a dominating set is a vertex subset D ⊆ V such that each vertex in
V − D is adjacent to at least one vertex in D. The goal of the Minimum Dominating Set problem
is to find a dominating set of the minimum size in a given graph. It is well known that the problem
is NP-hard [11]. It is therefore highly unlikely to develop algorithms that can solve the problem in
polynomial time.
Recently, a few exact algorithms have been developed to break the trivial O∗ (2n ) bound in the
time complexity of the minimum dominating set problem. In [9], it is shown that the number of
minimal dominating sets in a graph in n vertices is at most O(1.7159n ) and all these sets can be
enumerated in O(1.7159n ) time. In [10], it is shown that a minimum dominating set can be computed
in O(1.5264n ) time and polynomial space, the upper bound of the problem can be improved to
O(1.5137n ) in exponential space. The upper bound of the time complexity of this problem is further
improved to be O(1.5048n) in [20]. Although a large amount of efforts have been made to improve
the worst-case time complexity of the problem, it remains unknown whether it can be solved in
subexponential time or not. In [1], it is shown that it is very unlikely to solve a few NP-hard
problems in subexponential time, including the minimum dominating set problem.
Parameterized computation studies the possibility to develop efficient solutions to solve intractable optimization problems when the parameters in these problems are small integers. An
NP-hard problem is fixed parameter tractable if it is associated with a few parameters p1 , p2 , · · · , pm
and can be solved in time O(l(p1 , p2 , · · · , pm )nc ), where n is the size of the problem, l is a function
that only depends on the parameters and c is a constant independent of the parameters. A fixed

1

parameter tractable problem can be efficiently solved in practice if the parameters in the problem
are all small integers.
For example, the Vertex Cover problem is a well known fixed parameter tractable problem.
The goal of the problem is to decide whether a given graph G = (V, E) contains a vertex cover of size
k or not. Recent work has shown that the problem can be solved in time O(1.2852k + k|V |) [2]. On
the other hand, some NP-hard problems do not have known efficient parameterized solutions and
are thus believed to be parameterized intractable. The parameterized dominating set problem is one
of these problems. It has been shown that the problem is W[2]-complete [5, 6], which implies that
all problems in class W[2] are fixed parameter tractable if the problem is fixed parameter tractable.
This fact suggests that it is highly unlikely to develop efficient parameterized algorithms for the
parameterized dominating set problem. A comprehensive survey on parameterized computation
theory and complexity classes is provided in [4].
Since it is unlikely to develop algorithms that can efficiently solve NP-hard optimization problems,
a question arises naturally on whether approximate solutions with guaranteed approximation ratios
can be obtained for these problems in polynomial time. In [14] it is shown that the Minimum
Vertex Cover problem can be approximated within a ratio of 2.0 in polynomial time. For the
Minimum Dominating Set problem, a well known fact is that a greedy algorithm can achieve an
approximation ratio of ln n in polynomial time [14], where n is the number of vertices in the graph.
However, research in computational complexity also shows that some NP-hard problems cannot
be approximated within a certain ratio unless NP=P. For example, it is shown in [3] that the
Minimum Vertex Cover problem cannot be approximated within a ratio of 1.677 unless NP=P.
In [13], it is shown that it is NP-hard to approximate the maximum independent set of a graph
with a ratio of n1−ǫ in polynomial time, where n is the number of vertices in the graph and ǫ is
any positive constant. For the Minimum Dominating Set problem, it has been shown that the
problem cannot be approximated within a ratio of c ln n, where n is the number of vertices in the
graph and c is some positive constant independent of n [19]. A similar inapproximability result is
also obtained for the problem when the underlying graph is chordal or near chordal graphs [16, 17].
The Erdős-Rényi random graph model [8] has provided valuable insights into many problems
in both science and engineering. For example, recent research in molecular biology shows that
the protein side-chain interaction network can be described by a random graph generated with the
Erdos-Renyi model with high accuracy [15]. In this model, an edge appears between each pair
of vertices independently with a probability of p, where p is positive constant less than 1. When
p = 21 , each graph in n vertices is generated with equal probability and the model thus provides an
excellent platform to study the expected computational complexity of many NP-hard problems that
are formulated on graphs.
In [21], we show that the Maximum Independent Set problem can be solved in expected
O(log22 n)
2
time in a random graph generated with the Erdős-Rényi model in n vertices. In addition,
2
it is shown that the parameterized independent set problem can be solved in expected time 2O(k ) +
O(n3 ) and the Maximum Independent Set problem can be approximated within a ratio of √2n
2 log2 n
in expected polynomial time. All these results suggest that the expected computational complexity of
some NP-hard problems can be significantly different from its worst-case computational complexity.
A question therefore arises immediately on whether similar results can be obtained for other NP-hard
optimization problems or not, such as the Minimum Dominating Set problem.
In [18], an algorithm is developed to construct a near optimal dominating set for a random graph
G(n, p), where n is the number of vertices in the graph and p is a constant between 0 and 1 in
expected polynomial time. In [7], it is shown that a minimum dominating set contains O(log2 n)
vertices for almost all random graphs generated with the Erdős-Rényi model in n vertices. In [22],
it is shown that the domination number of a random graph enjoys a concentration as sharp as its
chromatic number. In [12], it is shown that the domination number of a random graph G(n, p) is
equal to one of the two values asymptotically almost surely whenever p is a constant between 0 and
1. These results all reveal that the size of a minimum dominating set is O(log2 n) in a random graph
1
. However, these available lower bounds in probability are not
with a probability at least 1 − nO(1)
sufficient to lead to an exact algorithm that can compute a minimum dominating set in a random
graph in expected subexponential time.
2

In this paper, we study the Dominating Set problem in random graphs generated based on the
Erdős-Rényi model. Using a new technique based on graph partition, we show that the problem can
2
be solved in expected 2O(log2 n) time. Although we are unable to develop an algorithm that can solve
the parameterized dominating set problem in expected O(f (k)nc ) time, we show that the expected
parameterized complexity of the problem is inherently related to its approximability in expected
polynomial time. In other words, we show that the parameterized dominating set problem can be
solved in expected time O(f (k)nc ) if and only if the Minimum Dominating Set problem can be
approximated within a ratio of o(log2 n) in expected polynomial time. In addition, our results also
suggest that the problem is fixed parameter tractable in expected sense when the probability p is a
1
, where g(n) < n is a monotonously increasing function of n and its
function of n and equals to g(n)
value approaches infinity when n approaches infinity.

2

Preliminaries and Notation

Given a graph G = (V, E) and vertex subset D ⊆ V , a vertex v ∈ G is dominated by D if v is
adjacent to at least one vertex in D. The domination number of G is the cardinality of a minimum
dominating set in G. Let m be a positive integer, a set of vertex
Smsubsets P1 , P2 , P3 , · · · , Pm in V is
a disjoint m-partition of G if all Pi ’s are pairwise disjoint and i=1 Pi = V . S
m
A partition P1 , P2 , P3 , · · · , Pm in V is a intersecting m-partition of G if i=1 Pi = V and it is
not a disjoint m-partition of G. Given a vertex v ∈ V , the degree of v in G is the number of vertices
that are adjacent to v in G. Let H = (U, F ) be a directed graph, the out-degree of a vertex u ∈ U
is the number of directed edges that start with u in F . The in-degree of u is the number of directed
edges that end with u in F .
We use G(n, p) (0 < p < 1) to denote a random graph generated with the Erdős-Rényi model in
n vertices. Each pair of vertices in G(n, p) are joined with an edge independently with a probability
of p.

3

The Algorithm

We start this section by showing that, with a probability of at least 1 − 2−O(n) , G(n, p) contains a
1
dominating set of size at most O(logq n), where q = 1−p
. The proof uses a technique based on a
disjoint partition of G(n, p). We then refine the result with a more sophisticated technique using
intersecting partitions of G(n, p).
Lemma 3.1 Given a random graph G(n, p) and a constant C > 1, where p is a constant between
C−1
0 and 1, with a probability at least 1 − n2 2− C n log2 q , G(n, p) contains a dominating set of size at
1
.
most C logq n, where q = 1−p
Proof. We assume that each dominating set in G(n, p) is larger than C logq n. We then arbitrarily
n
partition the vertices in G(n, p) into a l = ⌊ C log
⌋ + 1 disjoint partition P1 , P2 , P3 , · · · , Pl such
q n
that each of P1 , P2 , · · · , Pl−1 contains C logq n vertices and Pl contains at most C logq n vertices.
Given two subsets Pi and Pj in the partition, where 1 ≤ i ≤ l, 1 ≤ j ≤ l and i 6= j, Pi
is distinguished by Pj if Pj contains a vertex u such that u is not dominated by Pi . Since each
dominating set in G(n, p) contains at least C log2 n + 1 vertices, each subset in the partition is
distinguished by at least one other subset in the partition.
We now describe an algorithm that can be used to construct a directed graph H from the subsets
in the partition. Specifically, each subset in the partition is represented by a vertex in H and H thus
contains l vertices in total. We use u1 , u2 , · · · , ul to denote the vertices that represent P1 , P2 , · · · , Pl
respectively. ui is distinguished by uj if Pi is distinguished by Pj . The steps of the algorithm can
be described as follows.
1. Set M = {u1 } and s = u1 ;
2. use Ds to denote all vertices that distinguish s and arbitrarily select a vertex t ∈ Ds and create
a directed edge from s to t;
3

3. if t is not in M , update M to be M ∪ {t}, set s = t and go to step 2;
4. if t ∈ M , check whether M contains all l vertices in H or not; if it is not the case, arbitrarily
select a vertex g that is not in M , set s = g and go to step 2; otherwise, output H.
Since each vertex in H is distinguished by at least one other vertex in H, the above algorithm
constructs a directed graph H such that the out-degree of each vertex is 1. H thus contains l edges
in total.
We now consider the probability associated with an edge in H. We assume the edge is from ui
to uj . We use P (i, j) to denote this probability. It is clear that equation (1) holds for P (i, j).
P (i, j) = |Pj |(1 − p)|Pi |

(1)

We then use P (i) to denote the probability that ui is distinguished by a vertex in H. It is not
difficult to see that the following inequality holds for P (i).
P (i) ≤

l
X

P (i, j)

(2)

=

l
X

|Pj |(1 − p)|Pi |

(3)

j=1

j=1

= n(1 − p)|Pi |

(4)

Pl
where the second equality is due to the fact that j=1 |Pj | = n.
We use Ei to denote the event that ui is distinguished by another vertex as selected by the above
algorithm in H. It is clear that E1 , E2 , · · · , El are mutually independent. We use P to denote the
probability that G does not contain a dominating set of size C logq n. The following inequality holds
for P .
P

≤

l
Y

P (i)

(5)

i=1

≤ nl

l
Y

(1 − p)|Pi |

n

≤ n C logq n
2

(6)

i=1

= n 2

+2

(1 − p)n

− C−1
C n log2

where the third inequality is due to the fact that
thus follows.

Pl

i=1

(7)

q

|Pi | = n and l ≤

(8)
n
C log2 n

+ 2. The lemma

It is shown in [20] that a minimum dominating set can be computed in time O(1.5048n). Lemma
3.1 thus suggests that when p ≥ 21 , a large enough constant C can be selected such that, with a
probability of at least 1 − o(1.5048n ), G(n, p) contains a dominating set of size at most C logq n. A
minimum dominating set in G(n, p) can be computed with the following simple algorithm.
1. Exhaustively enumerate all subsets in G(n, p) that are of cardinality at most C logq n; for each
such subset, check whether it is a dominating set of G(n, p) or not;
2. if at least one dominating set is found, output the one that has the minimum cardinality;
otherwise use the algorithm developed in [20] to compute a minimum dominating set in G(n, p)
and output the result.
It is straightforward to see that the above algorithm can correctly compute a minimum dominating
2
set in G(n, p) in expected time 2O(log2 n) when p ≥ 12 .
4

However, it is also clear that Lemma 3.1 is not sufficient to guarantee that the expected com2
putation time of the above algorithm is 2O(log2 n) when p is a small constant. An improved lower
bound for P is thus needed to extend the above result to any constant p that satisfies 0 < p < 1.
We extend the disjoint partition we have used in the proof of Lemma 3.1 to a series of intersecting
partitions in G(n, p). Based on these intersecting partitions, we show that the lower bound for P
can be significantly improved.
Theorem 3.1 Given a random graph G(n, p) and a constant C > 3, where p is a constant between
C
1
1
0 and 1, with a probability at least 1 − n 2 logq n 2−( 6 − 2C )Cn log2 n , G(n, p) contains a dominating set
1
of size at most 32 C logq n, where q = 1−p
.
Proof. We assume that any dominating set in G(n, p) contains more than 32 C logq n vertices.
Similar to the proof of Lemma 3.1, a l disjoint partition P1 , P2 , · · · , Pl can be obtained in G(n, p),
n
⌋ + 1, each of P1 , P2 , · · · , Pl−1 contains C logq n vertices and Pl contains at most
where l = ⌊ C log
q n
C logq n vertices. We use L0 to denote this partition.
Since any dominating set in G(n, p) contains more than 32 C logq n vertices, each subset Pi in L0
is distinguished by at least one other subset in L0 . We consider using the following algorithm to
construct an intersecting partition L1 in G(n, p) from L0 .
1. Color each vertex in every subset in L0 to be red;
2. construct a directed graph H as described in the proof of Lemma 3.1;
3. set M = φ, S = {u1 , u2 , · · · , ul };
4. select a vertex ui ∈ S, find the directed edge that starts with ui in H, we use uj to denote the
other end of this directed edge;
5. since ui is distinguished by uj , there exists a vertex u ∈ Pj such that u is not dominated by
Pj . We update Pi to be Pi ∪ {u} and color u to be yellow in Pi and change the color of u to
be green in Pj ;
6. set M = M ∪ {ui } and S = S − {ui };
7. go to step 4 if S is not empty, otherwise output the partition formed by P1 , P2 , P3 , · · · , Pl as
L1 .
It is clear that the partition returned by the above algorithm is an intersecting partition. In
addition, different colors are assigned to vertices in each partition to clearly describe their different
origins or roles with respect to the partition. Specifically, each vertex u in L0 is initially colored to
be red. However, a vertex u that is later added from Pj to Pi is colored to be yellow and its color in
Pj is changed from red into green. We note here that since L1 is an intersecting partition, the color
of a vertex may change when a different subset that contains the vertex is considered.
Let Lk = {P1k , P2k , · · · , Plk } be an l-intersecting partition in G and each subset in Lk contains at
most 23 C logq n vertices. We use the following algorithm to construct a new intersecting partition
Lk+1 .
1. Set M = ǫ, S = {P1k , P2k , · · · , Plk };
2. select a subset Pik in S, arbitrarily choose a subset Pjk that distinguishes Pik in Lk−1 ;
3. find a vertex vik ∈ Pjk such that vik is not dominated by Pik ;
4. update Pik to be Pik ∪ {vik }, color vik to be yellow in Pik and color vik to be green in Pjk ;
5. update M to be M ∪ {Pik } and S to be S − {Pik };
6. go to step 2 if S is not empty, otherwise output P1k , P2k , · · · , Plk as Lk+1 .
5

Since each subset in Lk contains at most 32 C logq n vertices, step 2 of the above algorithm can
always find a subset Pjk that distinguishes Pik . We use Rk and Rk+1 to denote the numbers of red
vertices contained in Lk and Lk+1 respectively. The following lemma establishes the relationship
between them.
Lemma 3.2 Rk+1 ≥ Rk − l
Proof. We construct a directed graph Hk to describe the relationships among subsets in Lk . A
subset Pik is represented with a vertex ui in Hk . A directed edge (ui , uj ) is created from ui to uj if
Pik is distinguished by Pjk and Pjk is selected by the above algorithm. It is not difficult to see that
Hk contains l edges in total. The lemma follows from the fact that at most one red vertex is colored
into green when an edge is created in Hk .
For Lk , a subset Pik is partially distinguished by another subset Pjk if Pik does not contain red
vertices or there exists a vertex tkj ∈ Pjk such that tkj is not dominated by the set of red vertices
in Pik . We use Ek to denote the event that each subset in Lk is partially distinguished by another
subset in Lk . The following lemma establishes the independence of Ek+1 from E1 , E2 , · · · , Ek .
Lemma 3.3 Ek+1 is independent of E1 , E2 , · · · , Ek .
Proof. We consider an arbitrarily selected subset Pik in Lk . We use yi1 , yi2 , yi3 , · · · , yik to denote
the vertices that are included into Pik by the construction of L1 , L2 , · · · , Lk respectively. It is
straightforward to see that the vertex vik selected by the above algorithm is different from any of
yi1 , yi2 , yi3 , · · · , yik since vik is not contained in Pik . The lemma thus immediately follows.
1

1

Lemma 3.4 We use P (Ek ) to denote the probability of Ek+1 , then P (Ek ) ≤ n(1 − p)( 3 − C )n for
1
.
0 ≤ k ≤ C2 logq n, where q = 1−p

Proof. We use Rik to denote the number of red vertices in subset Pik in Lk . By Lemma 3.2, we
immediately obtain the following inequality.
l
X

Rik

i=1

≥

n − kl

≥

n
3

(9)
(10)

where the second inequality follows from the fact that k ≤

C
2

logq n and l ≤

n
C logq n

+ 1.

It is straightforward to see that the following inequality holds for P (Ek ) when 0 ≤ k ≤
P (Ek ) ≤
≤
≤
≤

l
Y

i=1
l

k

n(1 − p)Ri

n

n
1+ C log

qn

(1 − p)

1
( 31 − C
)n

n(1 − p)

logq n.
(11)

n

n (1 − p) 3

C
2

(12)
n
3

(13)
(14)

The lemma thus follows.
Starting with L0 , we can construct an intersecting partition L1 with the first algorithm described
in the proof. From L1 , we can construct h intersecting partitions L2 , L3 , · · · , Lh in G(n, p) where
h = C2 logq n with the second algorithm. Since each subset in Lk contains at most C logq n + k ≤
3C
2 logq n vertices, E1 , E2 , E3 , · · · , Eh must all occur. We use P to denote the probability that
G(n, p) does not contain a dominating set of size 32 C logq n. From Lemma 3.3 and Lemma 3.4, we

6

immediately obtain
≤

P

≤

h
Y

P (Ek )

h
Y

n(1 − p)( 3 − C )

(15)

k=1

k=1

1

1

1

1

≤ nh [(1 − p)( 3 − c ) ]h

= n

C
2

1
logq n −( 61 − 2C
)nC log2 n

2

(16)
(17)
(18)

The theorem thus follows.
From Theorem 3.1, we can immediately obtain the expected computation time needed to compute
a minimum dominating set in a random graph G(n, p).
Theorem 3.2 Given a random graph G(n, p) where p is a constant between 0 and 1, a minimum
1
dominating set in G(n, p) can be computed in expected time O(27 logq n log2 n ), where q = 1−p
.
Proof. When n is sufficiently large, we can set the constant C in Theorem 3.1 to be 4 and use the
following algorithm to compute a minimum dominating set in G(n, p).
1. Exhaustively enumerate all vertex subsets of cardinality at most 6 logq n and check if one of
them is a dominating set of G(n, p);
2. if at least one dominating set is found during the exhaustive search, return the one that is of the
minimum cardinality; otherwise, use the algorithm developed in [20] to compute a minimum
dominating set in G(n, p) and return the result.
By Theorem 3.1, the algorithm developed in [20] is called with a probability at most 2−O(n log2 n) .
The theorem thus follows.

4

Expected Parameterized Complexity and Approximability

In this section, we study the relationship between the expected parameterized complexity of the
Dominating Set problem and the expected approximability of the Minimum Dominating Set
problem in random graphs. We show that they are in fact inherently related to each other. To establish the connection between them, we first show that the Minimum Dominating Set problem can
be approximated within a ratio of o(log2 n) in expected polynomial time if the parameterized dominating set problem can be solved in expected O(f (k)nc ) time, where k is the size of the dominating
set and n is the number of vertices in the graph.
The following lemma is needed to prove the connection in this direction. It is originally proved
in [21]. We include the proof here for completeness.
Lemma 4.1 [21] Let G(n, p) be a random graph and ǫ be a sufficiently small positive number, where
2
p is a constant between 0 and 1. With a probability at least 1 − 2−µn , there exists a vertex u such
that its degree in G is at least (p − ǫ)n, where µ is a positive constant that only depends on ǫ and p.
2

Proof. We assume such a vertex does not exist in G(n, p), the graph thus contains at most (p−ǫ)n
2
edges. However, it is straightforward to see that the expected number of edges in G(n, p) is pn(n−1)
.
2
We use P to denote the probability that such a vertex does not exist, an upper bound for P can be
obtained based on the Chernoff bound.
P

≤

pn(n − 1) (nǫ − p)2
)
4
(p(n − 1))2
ǫ 2 n2
exp (−
)
32p

=

2− 32p ln 2

≤

exp (−

ǫ2 n2

(19)
(20)
(21)

7

where the second inequality holds for sufficiently large n. The lemma follows by letting µ =

ǫ2
32p ln 2 .

Given a random graph G(n, p) and a sufficiently small positive ǫ, a vertex u in G(n, p) is good if
its degree in G(n, p) is at least (p − ǫ)n. The following lemma states that a dominating set of size
2
O(log2 n) can be computed with a probability at least 1 − 2−O(log2 n) in polynomial time.
Lemma 4.2 Let G(n, p) be a random graph and D be a positive constant, where p is a constant
2
2
between 0 and 1. With a probability at least 1 − n2−µD log2 n , a dominating set of size at most
1
n + D log2 n can be found in polynomial time, where µ is some positive constant that only
log 1−p+ǫ
depends on p and ǫ.
Proof. We use the following algorithm to compute a dominating set in G(n, p).
1. Set G1 = G and S = φ;
2. return an empty set if G1 does not contain a good vertex; otherwise find a good vertex u ∈ G1 ;
3. update S to be S ∪ {u} and remove u and its neighbors from G1 ;
4. check whether the number of vertices in G1 is less than D log2 n vertices or not; if it is the
case, include all the vertices in G1 into S and return S; otherwise go to step 2.
It is clear that the above algorithm either returns a dominating set S of G(n, p) or an empty set
in polynomial time. Since a good vertex in G1 is included in S and all its neighbors are removed
from G1 when steps 2 and 3 are executed, the size of G1 is at most (1 − p + ǫ)r n after steps 2 and
3 are executed for r times. In addition, the algorithm returns when G1 contains less than D log2 n
vertices. Steps 2 and 3 are executed for at most log1−p+ǫ n times. The dominating set returned by
the algorithm thus contains at most log1−p+ǫ n + D log2 n vertices.
From Lemma 4.1, the algorithm terminates and returns an empty set in step 2 with a probability
2
at most 2−O(µ|V (G1 )| ) , where µ is a positive constant that only depends on p and ǫ and |V (G1 )| is
the number of vertices in G1 . Since G1 contains at least D log2 n vertices throughout the execution
of the algorithm. From union bound, we immediately conclude that the algorithm returns an empty
2
2
set with a probability at most n2−µD log2 n .
Theorem 4.1 Let G(n, p) be a random graph, where p is a positive constant between 0 and 1. The
minimum dominating set in G(n, p) can be approximated within a ratio of o(log2 n) if there exists an
algorithm that can determine whether G(n, p) contains a dominating set of size k or not in expected
time O(f (k)nc ), where c is a constant and f (k) is a monotonously increasing function that only
depends on k.
Proof. Since f (k) is a monotonously increasing function that only depends on k, there exists a
monotonously increasing function e(n) such that f (e(n)) is bounded from above by a polynomial of
n for sufficiently large n. In addition, e(n) approaches infinity as n approaches infinity.
We use A to denote the parameterized algorithm that can determine whether G(n, p) contains
a dominating set of size k or not in expected time O(f (n)nc ). In addition, we use B to denote the
algorithm developed in the proof of Lemma
4.2. Choose a sufficiently small positive number ǫ and
q
5
1
a positive constant D such that D > µ log q , where q = 1−p
and µ is as defined in Lemma 4.1.
2

We use the following algorithm to approximate a minimum dominating set in G(n, p).

1. Set the parameter k = e(n) and use A to determine whether G(n, p) contains a dominating
set of size k or not; if the answer is “yes”, set the parameter to be each integer between
1 and e(n) and apply A on G(n, p) for each parameter value to determine the size of the
minimum dominating set in G(n, p) and return the corresponding dominating set returned by
A; otherwise continue to execute step 2;
2. use B to find a dominating set in G(n, p); return the dominating set returned by B if it does
not return an empty set; otherwise continue to execute step 3;
8

3. exhaustively enumerate all subsets of cardinality at most 4 logq n in G(n, p) and check whether
a dominating set of G(n, p) can be found in them. If it is the case, return the dominating set
of the minimum cardinality; otherwise continue to execute step 4;
4. use the algorithm developed in [20] to compute a minimum dominating set in G(n, p) and
return the result.
It is straightforward to see that the above algorithm can approximate a minimum dominating
set in G(n, p) within a ratio of o(log2 n). Indeed, an exact solution is found if the algorithm returns
in step 1, 3, or 4. An approximate solution is returned in step 2. However, we know from Lemma
4.2 that the dominating set returned in step 2 contains at most O(log2 n) vertices. In addition, the
domination number of any G(n, p) processed by step 2 is larger than e(n) since the algorithm does
2n
not return in step 1. The approximation ratio of the algorithm is thus at most O( log
e(n) ) = o(log2 n).
We then consider the expected computation time needed by the algorithm. Step 1 needs expected
polynomial time since f (e(n)) is bounded from above by a polynomial of n. By Lemma 4.2, step 2
needs polynomial time. The amounts of computation time needed by steps 3 and 4 are O(n4 logq n )
and O(1.5048n ) respectively.
We use ET (n) to denote the expected computation time of the algorithm and ET3,4 (n) to denote
the expected computation time needed by the steps 3 and 4 altogether in the algorithm. In addition,
we use P3 (n) and P4 (n) to denote the probabilities that steps 3 and 4 are executed respectively.
2
2
By Lemma 4.2 and Theorem 3.1, we have P3 (n) ≤ n2−µD log2 n and P4 (n) ≤ 2O(−n log2 n) . The
following inequality thus holds for ET3,4 (n).
ET3,4 (n) ≤
≤
≤

L(P3 (n)n4 logq n + P4 (n)2n )
L(2
LH

−(µD2 − log4

2

2
q ) log2 n

n −O(n log2 n)

+2 2

(22)
)

(23)
(24)

whereqL and H are some constants independent of n. The third inequality is due to the fact that
5
n−O(n log2 n)
is bounded from above by a constant when n is sufficiently large.
D > µ log
q and 2
2

The algorithm thus needs expected polynomial time.

We then prove that the parameterized dominating set problem can be solved in expected O(f (k)nc )
time if the minimum dominating set problem can be approximated within a ratio of o(log2 n) in expected polynomial time. We need the following lemma to establish the connection in this direction.
Lemma 4.3 Let G(n, p) be a random graph, where n √
is a sufficiently large integer and p is a constant
between 0 and 1. With a probability at most exp (− 4n ), G(n, p) contains a dominating set of size
logq n
s(n) ,

where s(n) is a monotonously increasing function of n and its value approaches infinity when
n approaches infinity.
Proof. We assume G(n, p) contains such a dominating set D. We use P (D) to denote the probability for D to exist. Since each vertex in G − D is adjacent to at least vertex in D and G − D
contains at least n2 vertices when n is sufficiently large, P (D) must satisfy the following inequality.


logq n
n
n
(25)
P (D) ≤
logq n (1 − (1 − p) s(n) ) 2
s(n)

≤ n

1

logq n
s(n)

exp (−
√
n
≤ exp (−
)
4

n1− s(n)
)
4

(26)
(27)

where the second inequality is based on the fact that 1 − x < exp (− x2 ) when x is between 0 and
1. The third inequality holds for sufficiently large n since s(n) approaches infinity as n approaches
infinity. The lemma thus follows.
9

Theorem 4.2 Let G(n, p) be a random graph, where n is sufficiently large and p is a constant between 0 and 1. There exists an algorithm that can determine whether G(n, p) contains a dominating
set of size k or not in expected time O(f (k)nc ) if the minimum dominating set problem can be
approximated within a ratio of o(log2 n) in expected polynomial time, where f (k) is a function that
only depends on k and c is a constant independent of k and n.
log n

q
Proof. We denote the approximate algorithm by A and the approximation ratio of A is w(n)
,
1
where q = 1−p and w(n) is a monotonously increasing function. The value of w(n) approaches
infinity when n approaches infinity. We use the following algorithm to determine whether G(n, p)
contains a dominating set of size k or not.
p
1. If k > w(n), use the algorithm developed in [20] to compute a minimum dominating set in
G(n, p); return “yes” and the minimum dominating set found if k is greater than or equal to
the size of this dominating set; otherwise return “no”;

2. otherwise, apply A on G(n, p) to obtain an approximate solution S for a minimum dominating
set in G(n, p);
log n
3. if |S| ≤ √ q , exhaustively search all vertex subsets of cardinality k and check whether
w(n)

a dominating set can be found or not; if a dominating set is found return “yes” and the
dominating set; otherwise return “no”.

log n
4. return “no” if |S| > √ q ;
w(n)

p
It is clear from the description of the algorithm that when k > w(n), the algorithm correctly
p
determines whether G(n, p) contains a dominating set of size k or not in step 1. When k < w(n)
log n
and the cardinality of S is larger than √ q , the domination number of G(n, p) is larger than
w(n)
p
logq n
. The algorithm can thus recognize this case
w(n) since the approximation ratio of A is w(n)
p
log n
and correctly returns “no” in step 4. When k < w(n) and |S| ≤ √ q , the algorithm correctly
w(n)

determines whether G(n, p) contains a dominating set of size k by exhaustive search in step 3.
The computation time needed in step 1 is at most O(f (k)), where f (k) is a function of k. since
when k ≥ w(n), there exists a function z(k) such that n ≤ z(k). Step 1 thus needs O(f (k)) time.
Step 2 applies A to G(n, p) and thus needs expected polynomial
time. By Lemma 4.3, the probability
√
n
for the algorithm to execute step 3 is at most exp (− 4 ) when n is sufficiently large. We use ET3 (n)
to denote the expected computation time needed by step 3. ET3 (n) satisfies the following inequality
when n is sufficiently large.
√
n
ET3 (n) ≤ Lnk exp (−
)
(28)
4 √
√
n
)
(29)
≤ Ln w(n) exp (−
4
≤ LM
(30)
p
where L and M are constants independent of n and k. The second inequality holds since k ≤ w(n);
the third inequality holds since it is implied that w(n) < logq n when n is sufficiently large. The
theorem thus follows.

5

Extension to Sparse Random Graphs

In this section, we consider the case where the probability for an edge to appear between two
1
, where g(n) < n is a monotonously
vertices in G(n, p) is not a constant. We assume p = g(n)
increasing function of n and its value approaches infinity when n approaches infinity. We show that
the parameterized dominating set problem can be solved in expected O(f (k)nc ) time in this case.
10

The proof is based on the well known ln n-approximate algorithm for the minimum dominating set
problem.
1
Lemma 5.1 Let G(n, p) be a random graph and p = g(n)
, where g(n) < n is a monotonously
increasing
function
and
approaches
infinity
when
n
approaches
infinity. With a probability at most
√
1
exp (− 4n ), G(n, p) contains a dominating set of size g 3 (n) ln n.
Proof. Similar to the proof of Lemma 4.3, we assume G(n, p) contains such a dominating set D.
We use P (D) to denote the probability for D to exist. Since each vertex in G − D is adjacent to
at least vertex in D and G − D contains at least n2 vertices when n is sufficiently large, P (D) must
satisfy the following inequality.

P (D)

≤


1
n
n
(1 − (1 − p)g 3 (n) ln n ) 2
1
3
g (n) ln n



1

1

n

≤ ng 3 (n) ln n (1 − ng 3 (n) ln (1−p) ) 2
1
n
1
≤ exp (n 3 ln2 n)(1 −
)2
2
2
n g 3 (n)
2
1 1− 2
1
≤ exp (n 3 ln2 n) exp (− n g 3 (n) )
4
√
n
)
≤ exp (−
4

(31)
(32)
(33)
(34)
(35)

where the third inequality follows from the fact that ln (1 − p) > −2p when n is sufficiently large;
the fourth inequality is due to the fact that g(n) < n and 1 − x < exp (− x2 ) holds for x between 0
and 1; the last inequality holds when n is sufficiently large.
1
, where g(n) < n is a monotonously
Theorem 5.1 Let G(n, p) be a random graph and p = g(n)
increasing function and approaches infinity when n approaches infinity. There exists an algorithm
that can determine whether G(n, p) contains a dominating set of size k or not in O(f (k)nc ) time,
where f (k) is a function of k and c is a constant independent of n and k.
Proof. We use an algorithm similar to one developed in the proof of Theorem 5.1. Since it is well
known that a minimum dominating set can be approximated within a ratio of ln n with a greedy
algorithm in polynomial time [14]. We denote this approximation algorithm with B and we use the
following algorithm to determine whether G(n, p) contains a dominating set of size k or not.
1

1. If k > g 3 (n), use the algorithm developed in [20] to compute a minimum dominating set in
G(n, p); return “yes” and the minimum dominating set found if k is greater than or equal to
the size of this dominating set; otherwise return “no”;
2. otherwise, apply B on G(n, p) to obtain an approximate solution S for a minimum dominating
set in G(n, p);
1

3. if |S| ≤ g 3 (n) ln n, exhaustively search all vertex subsets of cardinality k and check whether
a dominating set can be found or not; if a dominating set is found return “yes” and the
dominating set; otherwise return “no”.
1

4. return “no” if |S| > g 3 (n) ln n;

1

Similar to the proof of Theorem 4.2, when k > g 3 (n), the algorithm correctly determines whether
G(n, p) contains a dominating set of size k or not in step 1. The computation time needed in this
1
1
step only depends on k. When k < g 3 (n) and the cardinality of S is larger than g 3 (n) ln n, the
1
domination number of G(n, p) is larger than g 3 (n) since the approximation ratio of B is ln n. The
1
algorithm can thus recognize this case and correctly returns “no” in step 4. When k < g 3 (n) and
1
|S| ≤ g 3 (n) ln n, the algorithm correctly determines whether G(n, p) contains a dominating set of
size k or not by exhaustive search in step 3.
11

Step 2 applies B to G(n, p) and thus needs polynomial
time. By Lemma 5.1, the probability for
√
the algorithm to execute step 3 is at most exp (− 4n ) when n is sufficiently large. We use ET3 (n)
to denote the expected computation time needed by step 3. It is straightforward to see that ET3 (n)
satisfies the following inequality when n is sufficiently large.
√
n
ET3 (n) ≤ Lnk exp (−
)
(36)
4 √
1
n
)
(37)
≤ Lng 3 (n) exp (−
4
≤ LM
(38)
1

where L and M are constants independent of n and k. The second inequality holds since k ≤ g 3 (n);
the third inequality holds since g(n) < n. The theorem thus follows.

6

Conclusions

In this paper, we study the dominating set problem in random graphs. We show that a minimum
2
dominating set can be computed in expected 2O(log2 n) time when the underlying graph is a random
graph G(n, p) generated based on the Erdős-Rényi model and p is a constant between 0 and 1. In
addition, we establish a close relation between the expected parameterized complexity and approximability of the problem in expected sense. We show that the parameterized dominating set problem
can be solved in expected O(f (n)nc ) time if and only if the minimum dominating set problem can
be approximated within a ratio of o(log2 n) in expected polynomial time. With a similar approach,
we show that the parameterized dominating set problem is fixed parameter tractable in expected
1
, where g(n) < n is a monotonously increasing function of n and
sense when the probability p = g(n)
its value approaches infinity when n approaches infinity.
Unfortunately, we are unable to develop an algorithm that can efficiently solve the parameterized
dominating set problem in expected sense. In [21], we show that the independent set problem is
fixed parameter tractable in expected sense. However, a well known fact is that the parameterized
independent set problem is W[1]-complete while the parameterized dominating set problem is W[2]complete. This suggests that the latter is more difficult to solve and it is therefore not surprising
that the expected parameterized complexity of this problem cannot be easily improved. Our future
work will focus on the possibility to improve the expected parameterized complexity of this problem.

References
[1] J. Chen, X. Huang, I. A. Kanj, and G. Xia, “Linear FPT Reductions and Computational Lower
Bounds”, Proceedings of the Thirty-Sixth ACM Symposium on Theory of Computing (STOC
2004), 212-221, 2004.
[2] J. Chen, I. A. Kanj, and G. Xia, “Improved Parameterized Upper Bounds for Vertex Cover”,
Proceedings of the Thirty-First International Symposium on Mathematical Foundations of Computer Science(MFCS 2006), 238-249, 2006.
[3] I. Dinur and S. Safra, “The Importance of Being Biased”, Proceeding of the Thirty-Fourth ACM
Symposium on Theory of Computing (STOC 2002), 33-42, 2002.
[4] R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1998.
[5] R. G. Downey and M. R. Fellows, “Fixed Parameter Tractibility and Completeness i: Basic
Theory”, SIAM Journal of Computing, 24:873-921, 1995.
[6] R. G. Downey and M. R. Fellows, “Fixed Parameter Tractibility and Completeness ii: Completeness for W[1]”, Theoretical Computer Science A, 141:109-131, 1995.

12

[7] P. Dryer, Ph.D. Dissertation, Department of Mathematics, Rutgers University, 2000.
[8] P. Erdős and A. Rényi, “On Random Graphs”, Publicationes Mathematicae, 6: 290-297, 1959.
[9] F. V. Fomin, F. Grandoni, A. Pyatkin, and A. Stepanov, “Combinatorial Bounds Via Measure
and Conquer: Bounding Minimal Dominating Sets and Applications”, ACM Transactions on
Algorithms, 5(1): 9: 1-17, 2008.
[10] F. V. Fomin, F. Grandoni, and D. Kratsch, “A Measure and Conquer Approach for the Analysis
of Exact Algorithms”, Journal of the ACM, 56(5):25:1-32, 2009.
[11] M. R. Garey and D. S. Johnson, Computers and Intractibility, W. H. Freeman and Co., San
Francisco, California, 1979. A guide to the theory of NP-completeness, A Series of Books in the
Mathematical Sciences.
[12] R. Glebov, A. Liebenau, and T. Szabo, “On the Concentration of the Domination Number of
the Random Graph”, arXiv: 1209.3115.
[13] J. Hastad, “Clique is hard to approximate within n1−ǫ ”, Proceedings of the Thirty-Seventh
Annual Symposium on Foundations of Computer Science (FOCS 1996), 627-636, 1996.
[14] D. S. Johnson, “Approximate Algorithms for Combinatorial Problems”, Journal of Computer
and System Sciences, 9, 256-278, 1974.
[15] O. Kuchaiev, T. Milenković, V. Memišević, W. Hayes, and N. Pržulj, “Topological Network Alignment Uncovers Biological Function and Phylogeny”, Journal of Royal Society
Interface,7(50):1341-1354, 2010.
[16] C. Liu and Y. Song, “Parameterized Dominating Set Problem in Chordal Graphs: Complexity
and Lower Bound”, Journal of Combinatorial Optimization, 18(1): 87-97, 2009.
[17] C. Liu and Y. Song, “Parameterized Complexity and Inapproximability of Dominating Set
Problem in Chordal and Near Chordal graphs”, Journal of Combinatorial Optimization, 22:
684-698, 2011.
[18] S. Nikoletseas and P. Spirakis, “Near Optimal Dominating Sets in Dense Random
Graphs”,Proceedings of the 19th Workshop on Graph-Theoretic Concepts in Computer Science,
1-10, 1993.
[19] R. Raz and S. Safra, “A Sub-Constant Error-Probability Low Degree Test, and a Sub-Constant
Error-Probability PCP Characterization of NP”, Proceedings of the Twenty-Ninth ACM Symposium on Theory of Computing (STOC 1997), 475-484, 1997.
[20] J. M. M. van Rooji, J. Nederlof, and T. C. van Dijk, “Inclusion/Exclusion Meets Measure and
Conquer: Exact Algorithms for Computing Minimum Dominating Sets”, Proceedings of the
Seventeenth Annual Symposium on Algorithms, 554-565, 2009.
[21] Y. Song, “On The Independent Set Problem in Random Graphs”, International Journal of
Computer Mathematics, 92(11): 2233-2242.
[22] B. Wieland and A. Godbole, “On The Domination Number of A Random Graph”, Electronic
Journal of Combinatorics, 8(1): 37-49, 2001.

13

