Some simplified NP-complete problems

ABSTRACT

It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted. First we show the completeness of SIMPLE MAX CUT (MAX CUT with edge weights restricted to value 1), and, as a corollary, the completeness of the OPTIMAL LINEAR ARRANGEMENT problem. We then show that even if the domains of the NODE COVER and DIRECTED HAMILTONIAN PATH problems are restricted to planar graphs, the two problems remain NP-complete, and that these and other graph problems remain NP-complete even when their domains are restricted to graphs with low node degrees. For GRAPH 3-COLORABILITY, NODE COVER, and UNDIRECTED HAMILTONIAN CIRCUIT, we determine essentially the lowest possible upper bounds on node degree for which the problems remain NP-complete.

REFERENCES

• 1: D. Adolphson and T. C. Hu, "Optimal Linear Ordering," SIAM J. Applied Math. 25 (1973), 403-423.
• 2: R. L. Brooks, "On Coloring the Nodes of a Network," Proc. Cambridge Philos. Soc., 37 (1941), 194-197.
• 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: J. Edmonds and E. L. Johnson, "Matching: A Well-Solved Class of Integer Linear Programs," Combinatorial Structures and Their Applications, Gordon and Breach (1970), 89-92.
• 5: S. Even , A. Pnueli , A. Lempel, Permutation Graphs and Transitive Graphs, Journal of the ACM (JACM), v.19 n.3, p.400-410, July 1972 [doi>10.1145/321707.321710]
• 6: M. R. Garey , R. L. Graham , J. D. Ullman, Worst-case analysis of memory allocation algorithms, Proceedings of the fourth annual ACM symposium on Theory of computing, p.143-150, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804907]
• 7: F. Gavril, "Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent set of a Chordal Graph," SIAM J. Computing 1 (1972), 180-187.
• 8: F. Gavril, "Algorithms for a Maximum Clique and a Maximum Independent Set of a Circle Graph," Networks 3 (1973), 261-273.
• 9: R. L. Graham, "Bounds on Multiprocessing Anomalies and Related Packing Algorithms," SJCC (1972), 205-217.
• 10: P. Herrmann, Reducibility among Combinatorial Problems, Masters Thesis, Massachusetts Institute of Technology (1973).
• 11: D. S. Johnson, "Fast Allocation Algorithms," SWAT (1972), 144-154.
• 12: David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
• 13: R. M. Karp, "Reducibility Among Combinatorial Problems," Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York (1972), 85-104.
• 14: B. W. Kernighan and S. Lin, "An Efficient Heuristic For Partitioning Graphs," BSTJ 49 (1970), 291-308.
• 15: S. Lin and B. W. Kernighan, "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," BSTJ 21 (1973), 498-516.
• 16: G. I. Orlova and Y. G. Dorfman, "Finding the Maximum Cut in a Graph," Eng. Cybernetics 10 (1972), 502-506.
• 17: S. Sahni, "Some Related Problems From Network Flows, Game Theory, and Integer Programming," SWAT (1972), 130-138.
• 18: Sartaj Kumar Sahni, On the knapsack and other computationally related problems., 1973
• 19: Ravi Sethi, Complete register allocation problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.182-195, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804049]
• 20: Larry Stockmeyer, Planar 3-colorability is polynomial complete, ACM SIGACT News, v.5 n.3, p.19-25, July 1973 [doi>10.1145/1008293.1008294]
• 21: J. D. Ullman, Polynomial complete scheduling problems, Proceedings of the fourth ACM symposium on Operating system principles, p.96-101, January 1973

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Theory