Minimum independent dominating set problem

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

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