Dominating Set

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Is there a dominating set of size $K$ or less for $G$, i.e. a subset $V' \subseteq V$ with $|V'| \leq K$ such that for all $u \in V - V'$ there is a $v \in V'$ for which $\{u,v\} \in E$?

Classes

• NP-complete

Comments

Remains NP-complete for planar graphs with maximum vertex degree 3 and planar graphs that are regular of degree 4 (Garey & Johnson, 1979). Variation in which the subgraph induced by $V'$ is required to be connected is also NP-complete, even for planar graphs that are regular of degree 4 (Garey & Johnson, 1979). Also NP-complete if $V'$ is required to be both a dominating set and an independent set. Solvable in polynomial time for trees (Cockayne et al., 1975). The related [problem:edge-dominating-set] problem, where we ask for a set $E' \subseteq E$ of $K$ or fewer edges such that every edge in $E$ shares at least one endpoint with some edge $E'$, is NP-complete, even for planar or bipartite graphs of maximum degree 3, but can be solved in polynomial time for trees (Yannakakis & Gavril, 1980), (Mitchell, 1977).

Proofs

NP-complete

Transformation from Vertex Cover.

Reducible from

• Vertex Cover

Reducible to

• Maximum Leaf Spanning Tree

References

• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.
• Cockayne, E., Goodman, S., & Hedetniemi, S. (1975). A linear algorithm for the domination number of a tree. Information Processing Letters, 4(2), 41–44. https://doi.org/10.1016/0020-0190(75)90011-3
• Yannakakis, M., & Gavril, F. (1980). Edge Dominating Sets in Graphs. SIAM Journal on Applied Mathematics, 38(3), 364–372. https://doi.org/10.1137/0138030
• Mitchell, S. (1977). Edge domination in trees. Proc. 8th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, 1977. https://ci.nii.ac.jp/naid/10022184453/en/