The node-deletion problem for hereditary properties is NP-complete
, and .
Journal of Computer and System Sciences 20 (2): 219 - 230 (1980)

We consider the family of graph problems called node-deletion problems, defined as follows; For a fixed graph property Π, what is the minimum number of nodes which must be deleted from a given graph so that the resulting subgraph satisfies Π? We show that if Π is nontrivial and hereditary on induced subgraphs, then the node-deletion problem for Π is NP-complete for both undirected and directed graphs.
  • @duerrschnabel
  • @dblp
This publication has not been reviewed yet.

rating distribution
average user rating0.0 out of 5.0 based on 0 reviews
    Please log in to take part in the discussion (add own reviews or comments).