Dominating Set Problem

Definition

Dominating Set Problem

Let be a graph and , whereby is part of the input (not a constant). The dominating set problem is a decision problem asking whether there exists a dominating set of , such that .

The following holds:

Relation to Vertex Cover

Let be a graph with no isolated vertices. Every vertex cover of is also a dominating set of .

Equivalence to Vertex Cover Problem

The dominating set problem is NP-hard and can be shown to be at least as hard as the vertex cover problem via polynomial time reduction.

Let be an instance of the vertex cover problem where is a graph with no isolated vertices.

We construct from in polynomial time as follows:

In a graph with no isolated vertices, every vertex cover is a dominating set, since every edge must be covered, implying every vertex is either in the cover or adjacent to a vertex in the cover.

Therefore, has a vertex cover of size if and only if has a dominating set of size .

Approaches

Brute-force

A brute-force approach tests all subsets of size and requires time to test whether a subset is a dominating set.

Time complexity:

Recursive

The recursive approach for dominating set uses the observation that for any vertex :

• Either (then we can remove and all its neighbours)
• Or one of ‘s neighbours is in (then we can remove that neighbour and its closed neighbourhood)

Time complexity: (using measure-and-conquer analysis)