Greedy Dominating Set (GDS)

Input

An undirected graph $G = (V, E)$ with a numbering on the vertices in $V$ and a designated vertex $u$.

Problem

Is vertex $u$ in the dominating set formed by the execution of the greedy dominating set algorithm?

Definitions

A dominating set $V’$ is a subset of $V$ such that for all $v \in V - V’$ there exists a vertex $w \in V’$ such that $\{v, w\} \in E$. We say $w$ covers $v$.

The greedy dominating set algorithm builds up a dominating set by placing the least numbered vertex that covers the most vertices in the dominating set. This procedure is repeated until all vertices are covered.

Status

$\P$-complete (Stewart [1]).

Remarks

The reduction to show hardness is from OHDVR.

This greedy heuristic is used to find ``small’’ dominating sets. It is well known that the general version of the problem called Dominating Set is $\NP$-complete (Garey and Johnson [2]).