Minimum independent dominating set problem

Minimum independent dominating set problem --- задача о минимальном независимом доминирующем множестве.

Given a graph $G=(V,e)$, the minimum independent dominating set problem (or MIDS) is the problem of finding the smallest possible set $S\subseteq V$ of vertices such that for all $u\in V-S$ there is $v\in S$ for which $(u,v)\in E$, and such that no two vertices in $S$ are joined by an edge in $E$. Variation in which the degree of $G$ is bounded by a constant $B$ is denoted by MIDS-B.