MINIMUM DOMINATING SET

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A dominating set for G, i.e., a subset $V' \subseteq V$ such that for all $u\in V-V'$ there is a $v\in V'$ for which $(u,v) \in E$.
• MEASURE: Cardinality of the dominating set, i.e., $\vert V'\vert$.

  
  

• Good News: Approximable within $1+\log\vert V\vert$ since the problem is a special instance of MINIMUM SET COVER [276].
• Bad News: Not approximable within $c\log \vert V\vert$, for some c > 0 [423].
• Comment: Equivalent to MINIMUM SET COVER under L-reduction [282] and [63]. See MINIMUM SET COVER for more comments. Not approximable within $(1-\varepsilon )\ln \vert V\vert$ for any $\varepsilon >0$, unless NP $\subset\mbox{\sc Dtime}(\vert V\vert^{\log\log\vert V\vert})$ [153]. Complete for the class of $\log$-approximable problems [305]. Admits a PTAS for planar graphs [53] and for unit disk graphs [264]. Variation in which the degree of G is bounded by a constant B is APX-complete for $B \ge 3$ [393] and is approximable within $\sum_{i=1}^{B+1} \frac{1}{i}-1/2$ by reduction to MINIMUM SET COVER. The bad news hold also for bipartite graphs and split graphs (observation). If the dominating set is restricted to be connected the problem is approximable within $\ln\Delta+3$ where $\Delta$ is the maximum degree, and within $3\ln\vert V\vert$ for the vertex weighted version [208].
• Garey and Johnson: GT2