Edge-Deletion Problems

Abstract

If $\pi $ is a property on graphs or digraphs, the edge-deletion problem can be stated as follows: find the minimum number of edges whose deletion results in a subgraph (or subdigraph) satisfying property $\pi $. Several well-studied graph problems can be formulated as edge-deletion problems.In this paper we show that the edge-deletion problem is NP-complete for the following properties: (1) without cycles of specified length l, or of any length $ \leqq l$, (2) connected and degree-constrained, (3) outerplanar, (4) transitive digraph, (5) line-invertible, (6) bipartite, (7) transitively orientable. For problems (5), (6), (7) we determine the best possible bounds on the node-degrees for which the problems remain NP-complete.