Dominating Set Problem

computation graph-theory

Definition

Dominating Set Problem

Let $G=(V,E)$ be a graph and $k\in \mathbb{Z}$, whereby $k$ is part of the input (not a constant). The dominating set problem is a decision problem asking whether there exists a dominating set $D$ of $G$, such that $|D|\le k$.

The following holds:

$$G\text{ has dominating set }D\text{ with }|D|=k⟹n\le k+\left(\genfrac{}{}{0ex}{}{k}{2}\right)$$

Relation to Vertex Cover

Let $G=(V,E)$ be a graph with no isolated vertices. Every vertex cover of $G$ is also a dominating set of $G$.

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.

$\text{VERTEX COVER}{\le }_P\text{DOMINATING SET}$

Let $(G,k)$ be an instance of the vertex cover problem where $G=(V,E)$ is a graph with no isolated vertices.

We construct $G^{\prime }$ from $G$ in polynomial time as follows:

$G^{\prime }=G$

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, $G$ has a vertex cover of size $\le k$ if and only if $G^{\prime }$ has a dominating set of size $\le k$.

Approaches

Brute-force

A brute-force approach tests all $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=O(n^k)$ subsets of size $k$ and requires $O(k(n+m))$ time to test whether a subset is a dominating set.

Time complexity: $O(k(n+m)n^k)$

Recursive

The recursive approach for dominating set uses the observation that for any vertex $v\in V$:

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

Time complexity: $O(1.6181^n)$ (using measure-and-conquer analysis)