Edge-deletion and edge-contraction problems
- 1 January 1982
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 245-254
- https://doi.org/10.1145/800070.802198
Abstract
For a property -&-pgr; on graphs, the corresponding edge-deletion problem PED(-&-pgr;) (edge-contraction problem PEC(-&-pgr;), 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 -&-pgr;. In this paper we show that the edge-deletion problem PED (-&-pgr;) (edge-contraction problem PEC (-&-pgr;), resp.) is NP-hard if -&-pgr; is hereditary on subgraphs (contractions, resp.) and is determined by the 3-connected components.Keywords
This publication has 0 references indexed in Scilit: