Node- and Edge-Deletion NP-Complete Problems

If π is a graph property, the general node(edge) deletion problem can be stated as follows: Find the minimum number of nodes(edges), whose deletion results in a subgraph satisfying property π. In this paper we show that if π belongs to a rather broad class of properties (the class of properties that are hereditary on induced subgraphs) then the node-deletion problem is NP-complete, and the same is true for several restrictions of it. For the same class of properties, requiring the remaining graph to be connected does not change the NP-complete status of the problem; moreover for a certain subclass, finding any "reasonable" approximation is also NP-complete. Edge-deletion problems seem to be less amenable to such generalizations. We show however that for several common properties (e.g. planar, outer-planar, line-graph, transitive digraph) the edge-deletion problem is NP-complete.

Authors

• Mihalis Yannakakis

Keywords

• NP-complete
• Graph
• Node-deletion
• Approximation
• Polynomial hierarchy
• Computational complexity
• Graph-property
• Maximum subgraph
• Hereditary
• Edge-deletion