TY - JOUR

T1 - The Complexity of Some Edge Deletion Problems

AU - El-Mallah, Ehab S.

AU - Colbourn, Charles J.

N1 - Funding Information:
Manuscript received May 27, 1987; revised October 19, 1987. C. J. Colbourn's research was supported by NSERC Canada under Grant A0579. This paper was recommended by K. Thulasiraman and N. Deo, Guest Editors for this issue.

PY - 1988/3

Y1 - 1988/3

N2 - The edge deletion problem (EDP) corresponding to a given class H of graphs is to find the minimum number of edges whose deletion from a given graph G results in a subgraph G', G' - H. In this paper we extend previous complexity results by showing that the EDP corresponding to any class H of graphs in each of the following cases is NP-hard. (i) H is defined by a set of forbidden homeomorphs or minors in which every member is a 2-connected graph with minimum degree 3. (ii) H is defined by K4 — e as a forbidden homeomorph or minor. (iii) H is defined by Pl, l - 3, the simple path on l nodes, as a forbidden induced subgraph.

AB - The edge deletion problem (EDP) corresponding to a given class H of graphs is to find the minimum number of edges whose deletion from a given graph G results in a subgraph G', G' - H. In this paper we extend previous complexity results by showing that the EDP corresponding to any class H of graphs in each of the following cases is NP-hard. (i) H is defined by a set of forbidden homeomorphs or minors in which every member is a 2-connected graph with minimum degree 3. (ii) H is defined by K4 — e as a forbidden homeomorph or minor. (iii) H is defined by Pl, l - 3, the simple path on l nodes, as a forbidden induced subgraph.

UR - http://www.scopus.com/inward/record.url?scp=0023981241&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023981241&partnerID=8YFLogxK

U2 - 10.1109/31.1748

DO - 10.1109/31.1748

M3 - Article

AN - SCOPUS:0023981241

SN - 0098-4094

VL - 35

SP - 354

EP - 362

JO - IEEE transactions on circuits and systems

JF - IEEE transactions on circuits and systems

IS - 3

ER -