Generalizing NP-completeness proofs for bipartite graphs and chordal graphs
Alice A. McRae · TigerPrints (Clemson University) · 1995
In this dissertation, we focus on developing general NP-complete constructions and applying them to a number of related graph problems. We will present original NP-completeness results, some of which are new, and others which are simpler proofs of existing NP-completeness results (see Table 2 and Table 3 in Chapter 6). 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.