MINIMUM INDEPENDENT DOMINATING SET

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: An independent 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$, and such that no two vertices in V' are joined by an edge in E.
• MEASURE: Cardinality of the independent dominating set, i.e., $\vert V'\vert$.

  
  

• Bad News: Not approximable within $\vert V\vert^{1-\varepsilon }$ for any $\varepsilon >0$ [220].
• Comment: Also called Minimum Maximal Independent Set. Under the assumption that $NP \not\subseteq \mbox{\sc Dtime}(2^{o(n)})$, the problem is not approximable within $\vert V\vert/\log^{1+\varepsilon } \vert V\vert$, for any $\varepsilon >0$. The problem is also NPO PB-complete [284]. Variation in which the degree of G is bounded by a constant B is trivially approximable within B, and is APX-complete [282]. Approximable within 5 for unit disk graphs [370]. Not approximable within $\vert V\vert^{1-\varepsilon }$ even for circle graphs and bipartite graphs [132]. The maximization variation in which the set $\{0,1,\ldots,k\}$ for some fixed k constrains how the independent set can dominate the remaining vertices is approximable within $O(\sqrt{\vert V\vert})$ and is not approximable within $\vert V\vert^{1/(k+1)-\varepsilon }$ for any $\varepsilon >0$ unless $NP=\mbox{\sc Zpp}$ [229].
• Garey and Johnson: GT2