Analysis of a Greedy Heuristic For Finding Small

Dominating Sets in Graphs

(To appear in Information Processing Letters)

Abhay K. Parekh
Laboratory For Information and Decision Systems, M.I.T., Cambridge, MA 02139, USA

Abstract
We analyze a simple greedy algorithm for finding small dominating sets in undi-
√
rected graphs of N nodes and M edges. We show that dg ≤ N + 1 − 2M + 1, where
dg is the cardinality of the dominating set returned by the algorithm.
Keywords: approximate algorithms, analysis of algorithms.

Introduction
Let G(V, E) be an undirected graph with N nodes and M edges. A dominating
set of G is a set of nodes such that every node not in the set is adjacent to at least
one node in the set. A dominating set of smallest cardinality is known as a minimum
dominating set. The problem of finding a minimum dominating set is combinatorially
hard (its decision version is NP-complete [2]), so as a practical matter, one has to settle
for approximate, but fast algorithms. In this note, we analyze the performance of a
simple, greedy algorithm of this type. Let dg be the size of the dominating set returned
by the greedy algorithm, and let do be the cardinality of a minimum dominating set.
We show that an upper bound on do due to Vizing [5], applies to dg as well:
√
dg ≤ N + 1 − 2M + 1.

Previous Work
The greedy algorithm considered here is an analog of one that has been analyzed
by Chvatal [1] and others [3], [4] for finding small set covers. The focus there has
been on comparing the cardinality of the set cover returned by the algorithm to that
of the smallest set cover, in the worst case. Since any dominating set problem can be
formulated as a set covering problem, the results for the set covering algorithm can be
PAGE
 A. K. PAREKH

specialized to our problem. A result almost directly obtained from the work of Chvatal
[1] is that
δ+1
dg X 1
≤ ,
do i=1
i
where δ is the maximum degree of a node in the graph. The result of this paper describes
the performance of the algorithm in terms of the dimensions of the graph, and should
be viewed as complementary to the above result.
Greedy: The Approximation Algorithm
Let V = {1, ..., N }, and define D = φ. Greedy adds a new node to D in each
iteration, until D forms a dominating set. A node, j, is said to be “covered” if j ∈ D
or if any neighbor of j is in D. A node that is not covered is said to be uncovered.
(Since D = φ at the beginning of the algorithm, it follows that all the nodes are
initially uncovered.) In each iteration, put into D the least indexed node that covers the
maximum number of uncovered nodes. Stop when all the nodes are covered. (Selecting
the least numbered element is just a way of breaking ties.) An example of Greedy at
work is provided in Figure 1.
Worst Case Performance in terms of N and M
Here we show that an upper bound on do due to Vizing [5] is met by dg as well:
Theorem 1. For an undirected graph, G, with N nodes and M edges:
√
dg ≤ N + 1 − 2M + 1. (1)

Proof: First convert G into a directed graph by replacing every edge {i, j} by 2 directed
edges (i,j) and (j,i), and by adding self-loops (i,i) at every node i. Define the outdegree
of a node as the number of edges emanating from it. Any node j, such that (n, j) is an
edge in the directed graph, is said to be in the out-neighborhood of n. We can interpret
Greedy on the constructed directed graph as follows: Include the least indexed node,
n, with the greatest outdegree in the dominating set; delete all edges coming into any
node in the out-neighborhood of n; and if there are any edges left, include another node
in the dominating set, else stop. To see that this is identical to Greedy, interpret a
directed edge (i,j) to mean that if i were included in the dominating set, the previously
uncovered node, j, would be covered by i (see figure 2).
Suppose Greedy picks node vi in the ith iteration. Let S(i) be the set of previously
uncovered nodes which were covered by vi , and let |S(i)| = mi . Finally, define Ei to be
PAGE
 Finding Small Dominating Sets

the number of edges left at the end of the ith iteration coming from uncovered nodes,
i.e., Ei does not include edges from covered nodes. Set E0 = 2M + N , and also notice
that Edg = 0. (Observe that when there are no edges left, we have found a dominating
set.) Our strategy in the proof is the following: We first find a lower bound on E 0 in
terms of the mi ’s. Next, we show that this lower bound is no greater than a particular
expression that is independent of the mi ’s. Algebraic simplification completes the proof.
First we show that at most m2i edges from previously uncovered nodes are deleted
in the ith iteration. Consider some j ∈ S(i). The outdegree of j can be at most m i
just before the ith iteration. Now notice that no edges into an uncovered node can
be deleted before the node is covered. Since j is uncovered before the ith iteration,
for each edge coming into j from a uncovered node, there is also an edge going out of
j to that uncovered node. Thus there can be at most mi edges coming into j from
uncovered nodes, and the total number of edges running from previously uncovered
nodes to members in S(i) is at most m2i . There may also be edges from previously
covered nodes to members of S(i), but we need not consider them, since we are counting
(in Ei ) only edges from uncovered nodes.
Next, we estimate the number of edges from S(i) to uncovered nodes which are
not in S(i). These edges are not deleted by Greedy, but they are not counted in
the definition of Ei either. It is clear that the outdegree of every node in S(i) must
be ≤ mi − 1, since the self loops of all such nodes will have been deleted in the ith
step. Thus the number of outgoing edges from S(i), after iteration i is ≤ m i (mi − 1).
However, in the first and last iterations, we can tighten this bound slightly. We know
that v1 ∈ S(1), and so all edges entering and leaving v1 will be deleted after the first
iteration. Further, the other nodes in S(1) can have outdegree of at most m 2 at the
end of the first iteration. Thus, the number of edges (at the end of the first iteration)
from S(1) to uncovered nodes not in S(1) is at most (m1 − 1)m2 . Finally, note that no
edges remain at the end of the last iteration, and so the number of edges from S(d g ) to
uncovered nodes must be zero.
By the definition of Ei , we conclude that for 2 ≤ i < dg :

Ei ≥ Ei−1 − m2i − mi (mi − 1).

For the special cases, i = 1 and i = dg :

E1 ≥ Eo − m21 − (m1 − 1)m2 ,

and
Edg ≥ Edg −1 − m2dg .
PAGE
 A. K. PAREKH

Edg = 0 by the definition of dg . Thus,

 
dg dg −1
X X
0 = E dg ≥ −  m2i + (m1 − 1)m2 + mi (mi − 1) + E0 .
i=1 i=2

Solving for E0 :
dg dg −1
X X
E0 ≤ m2i + (m1 − 1)m2 + mi (mi − 1). (2)
i=1 i=2
P dg
Now notice that i=1 mi = N , and that m1 ≥ m2 ≥ ... ≥ mdg ≥ 1. We claim that
the RHS of (2) attains its maximum with respect to the mi ’s subject to the constraints
just mentioned, when

m1 = N − dg + 1, m2 = m3 = ...mdg = 1.

This is easily seen to be true by contradiction. Suppose the maximum is achieved so

that the highest order mi which is greater than 1 is not m1 , but say mj , j > 1. Now
reduce mj to 1 and add mj − 1 to m1 (we can do this because none of the constraints
is violated), and the difference in the RHS is seen to be non-negative. This contradicts
the assumption.
Substituting the maximum values in the RHS of (2) we have:

E0 = 2M + N ≤ (N − dg + 1)2 + dg − 1 + (N − dg ),

√
⇒ dg ≤ N + 1 − 2M + 1.
Done
The bound of Theorem 1 is met exactly by graphs of the type shown in Figure 3.
Acknowledgment
I am grateful to Professor Robert Gallager for his help in the performing and writing
of this work.
References
[1] V. Chvatal, A Greedy Heuristic for the Set Covering problem, Mathematics of
Operations Research, 4, (1979) 233-235.
[2] M. R. Garey, D. S. Johnson, Computers and Intractability - A Guide to the Theory
of NP-Completeness, (W. H. Freeman, San Francisco CA, 1979.)
[3] D. S. Hochbaum, Approximation Algorithms for the Set Covering and Vertex Cov-
ering Problems, SIAM Journal on Computing, 11, (1982) 555-556.
PAGE
 Finding Small Dominating Sets

[4] D. S. Johnson, Approximate Algorithms for Combinatorial Problems, Journal of

Computer System Science, 9, (1974) 256-278.
[5] V. G. Vizing, A Bound on the External Stability Number of a Graph, Doklady A.
N., 164, (1965) 729-731.

PAGE
 A. K. PAREKH

3 5 2
4

7 1

{1, 2, 3}{2, 3}

PAGE
 Finding Small Dominating Sets

3 5

2
4

7 1

(a)

3 5

2
4

7 1

GreedyE1 = 2 (b)

PAGE
 A. K. PAREKH

3
8 10
2
4

1
7
5 11

13 6

12√49 = 7d
{1, 2, ..., 7}N = 13, M = 247 = dg ≤ 14 − = 6{2, 3, ..., 7}
o

PAGE