Another example is the perfect dominating set problem also known as efficient dominating set or 1-perfect code in graphs. The problem is to decide the existence of a dominating set $C$ such that the shortest path between any two nodes in the dominating set $C$ is at least 3 (edges). The problem was proven to be $NP$-complete independently by many researchers. The problem remains $NP$-complete even for cubic planar graphs.
Mohammad Al-Turkistany
- 21.1k
- 5
- 66
- 152