Node-Deletion NP-Complete Problems
Mukkai S. Krishnamoorthy, Narsingh Deo · SIAM Journal on Computing · 1979
The entire class of node-deletion problems can be stated as follows: Given a graph G, find the minimum number of nodes to be deleted so that the remaining subgraph g satisfies a specified property $\pi $. For each $\pi $, a distinct node-deletion problem arises. The various deletion problems considered here are for the following properties: each component of g is (i) null, (ii) complete, (iii) a tree, (iv) nonseparable, (v) planar, (vi) acyclic, (vii) bipartite, (viii) transitive, (ix) Hamiltonian, (x) outerplanar, (xi) degree-constrained, (xii) line invertible, (xiii) without cycles of a specified length, (xiv) with a singleton K-basis, (xv) transitively orientable, (xvi) chordal, and (xvii) interval. In this paper, these 17 different node-deletion problems are shown to be NP-complete. A unified approach is taken for the transformations employed in the proofs.