ABSTRACT
We present original NP-completeness results and new and simpler proofs of existing NP-completeness results for domination-related parameters (see Tables 9.2 and 9.3). All of the proofs of these results are no longer than two pages; most are less than one page long. The great majority of these results use reductions from the Exact Cover by 3 Sets Problem and use a common graph construction. The full generality of this technique has not been fully developed, and we suggest a number of “open” problems that may be shown NP-complete by applying similar techniques. We conclude by providing a compendium of other original NP-completeness proofs not contained in this chapter but which use similar proof constructions.
