Edge-deletion and edge-contraction problems
Takao Asano, Tomio Hirata · 1982
For a property π on graphs, the corresponding edge-deletion problem PED(π) (edge-contraction problem PEC(π), resp.) is defined as follows: Given a graph G, find a set of edges of minimum cardinality whose deletion (contraction, resp.) results in a graph satisfying property π. In this paper we show that the edge-deletion problem PED (π) (edge-contraction problem PEC (π), resp.) is NP-hard if π is hereditary on subgraphs (contractions, resp.) and is determined by the 3-connected components.