Node-and edge-deletion NP-complete problems

ABSTRACT

If &pgr; is a graph property, the general node(edge) deletion problem can be stated as follows: Find the minimum number of nodes(edges), whose deletion results in a subgraph satisfying property &pgr;. In this paper we show that if &pgr; belongs to a rather broad class of properties (the class of properties that are hereditary on induced subgraphs) then the node-deletion problem is NP-complete, and the same is true for several restrictions of it. For the same class of properties, requiring the remaining graph to be connected does not change the NP-complete status of the problem; moreover for a certain subclass, finding any "reasonable" approximation is also NP-complete. Edge-deletion problems seem to be less amenable to such generalizations. We show however that for several common properties (e.g. planar, outer-planar, line-graph, transitive digraph) the edge-deletion problem is NP-complete.

REFERENCES

• 1: Giorgio Ausiello , Alessandro D'Atri , Marco Protasi, On the Structure of Combinatorial Problems and Structure Preserving Reductions, Proceedings of the Fourth Colloquium on Automata, Languages and Programming, p.45-60, July 18-22, 1977
• 2: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 3: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 4: S. Even, "Maximal flow in a network and the connectivity of a graph," Proc. of Eighth Annual Princeton Conf. on Info. Sci. and Systems (1974), 470-472.
• 5: J. Edmonds, "Paths Trees and Flowers", Can. J. Math. 17 (1965), 449-467.
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: M. R. Garey, D. S. Johnson, and L Stockmeyer, "Some simplified NP-complete graph problems", Theoretical Comp. Science 1 (1976), 237-267.
• 8: F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1970.
• 9: D. J. Johnson, "Approximation algorithms for combinatorial problems", J. Comp. System Sci. 9(1974), 256-278.
• 10: R. M. Karp, "Reducibility among combinatorial problems", in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., Plenum Press, NY, 1972, 85-103.
• 11: M. S. Kirshnamoorthy and N. Deo, "Node-deletion NP-complete problems", Computer Science Program, Indian Institute of Technology, report, (1977).
• 12: E.W. Legged Jr., "Tools and techniques for classifying problems", Ph.D. Thesis, Dept. of Comp. and Info. Sciences, Ohio State Univ. (1977).
• 13: John M. Lewis, On the complexity of the Maximum Subgraph Problem, Proceedings of the tenth annual ACM symposium on Theory of computing, p.265-274, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804356]
• 14: J. M. Lewis, D. P. Dobkin, and R. J. Lipton, "Graph properties defined by a forbidden subgraph", Proc. of the 1977 Conference on Info. Sci. and Systems, 108-112.
• 15: D. Plaisted, "Some polynomial and integer divisibility problems are NP-hard", 17th Annual IEEE Symp. on Foundations of Computer Science (1976), 264-267.
• 16: D. Plaisted, "New NP-hard and NP-complete polynomial and integer divisibility problems", 18th Annual IEEE Symp. on Foundations of Computer Science (1977), 241-253.
• 17: L. Stockmeyer, "The polynomial time hierarchy", Theoretical Comp. Sci. 3(1977), 1-22.
• 18: R. Endre Tarjan, Testing graph connectivity, Proceedings of the sixth annual ACM symposium on Theory of computing, p.185-193, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803897]
• 19: R. E. Tarjan, "Depth-first-search and linear graph algorithms", SIAM J. on Computing 1(1972), 146-160.
• 20: M. Yannakakis, "Node-deletion problems on bipartite graphs", Technical report, Computer Science Lab., Princeton University, 1978
• 21: M. Yannakakis, "The effect of a connectivity requirement on the complexity of maximum sub-graph problems", Technical report, Computer Science Lab., Princeton University, 1978.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Theory

Keywords:
Approximation, Computational complexity, Edge-deletion, Graph, Graph-property, Hereditary, Maximum subgraph, NP-complete, Node-deletion, Polynomial hierarchy