Skip to main content
Springer Nature Link
Log in

Exact Algorithms for NP-Hard Problems: A Survey

  • Chapter
  • First Online:
Combinatorial Optimization — Eureka, You Shrink!

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2570))

Abstract

We discuss fast exponential time solutions for NP-complete problems. We survey known results and approaches, we provide pointers to the literature, and we discuss several open problems in this area. The list of discussed NP-complete problems includes the travelling salesman problem, scheduling under precedence constraints, satisfiability, knapsack, graph coloring, independent sets in graphs, bandwidth of a graph, and many more.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 53.49
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. K.A. Abrahamson, R.G. Downey, and M.R. Fellows [1995]. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic 73, 235–276.

    Google Scholar 

  2. D. Applegate, R. Bixby, V. Chvátal, and W. Cook [1998]. On the solution of travelling salesman problems. Documenta Mathematica 3, 645–656.

    Google Scholar 

  3. R. Beigel [1999]. Finding maximum independent sets in sparse and general graphs. Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA’1999), 856–857.

    Google Scholar 

  4. R. Beigel and D. Eppstein [1995]. 3-Coloring in time O(1.3446n): A no-MIS algorithm. Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS’1995), 444–453.

    Google Scholar 

  5. J. Chen, I.A. Kanj, and W. Jia [1999]. Vertex cover: Further observations and further improvements. Proceedings of the 25th Workshop on Graph Theoretic Concepts in Computer Science (WG’1999), Springer, LNCS 1665, 313–324.

    Google Scholar 

  6. E. Dantsin, A. Goerdt, E.A. Hirsch, R. Kannan, J. Kleinberg, C.H. Papadimitriou, P. Raghavan, and U. Schöning [2001]. A deterministic (2-2/k+1)n algorithm for k-SAT based on local search. To appear in Theoretical Computer Science.

    Google Scholar 

  7. R.G. Downey and M.R. Fellows [1992]. Fixed parameter intractability. Proceedings of the 7th Annual IEEE Conference on Structure in Complexity Theory (SCT’1992), 36–49.

    Google Scholar 

  8. R.G. Downey and M.R. Fellows [1999]. Parameterized complexity. Springer Monographs in Computer Science.

    Google Scholar 

  9. L. Drori and D. Peleg [1999]. Faster exact solutions for some NP-hard problems. Proceedings of the 7th European Symposium on Algorithms (ESA’1999), Springer, LNCS 1643, 450–461.

    Google Scholar 

  10. D. Eppstein [2001]. Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA’2001), 329–337.

    Google Scholar 

  11. D. Eppstein [2001]. Small maximal independent sets and faster exact graph coloring. Proceedings of the 7th Workshop on Algorithms and Data Structures (WADS’2001), Springer, LNCS 2125, 462–470.

    Google Scholar 

  12. U. Feige and J. Kilian [1997]. On limited versus polynomial nondeterminism. Chicago Journal of Theoretical Computer Science (http://cjtcs.cs.uchicago.edu/).

  13. U. Feige and J. Kilian [2000]. Exponential time algorithms for computing the bandwidth of a graph. Manuscript.

    Google Scholar 

  14. M.R. Garey and D.S. Johnson [1979]. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.

    Google Scholar 

  15. J. Gramm and R. Niedermeier [2000]. Faster exact solutions for Max2Sat. Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC’2000), Springer, LNCS 1767, 174–186.

    Google Scholar 

  16. M. Held and R.M. Karp [1962]. A dynamic programming approach to sequencing problems. Journal of SIAM 10, 196–210.

    Google Scholar 

  17. T. Hofmeister, U. Schöning, R. Schuler, and O. Watanabe [2001]. A probabilistic 3-SAT algorithm further improved. Manuscript.

    Google Scholar 

  18. E. Horowitz and S. Sahni [1974]. Computing partitions with applications to the knapsack problem. Journal of the ACM 21, 277–292.

    Google Scholar 

  19. R.Z. Hwang, R.C. Chang, and R.C.T. Lee [1993]. The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica 9, 398–423.

    Google Scholar 

  20. R. Impagliazzo and R. Paturi [2001]. Complexity of k-SAT. Journal of Computer and System Sciences 62, 367–375.

    Google Scholar 

  21. R. Impagliazzo, R. Paturi, and F. Zane [1998]. Which problems have strongly exponential complexity? Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS’1998), 653–663.

    Google Scholar 

  22. T. Jian [1986]. An O(20.304n) algorithm for solving maximum independent set problem. IEEE Transactions on Computers 35, 847–851.

    Google Scholar 

  23. D.S. Johnson and M. Szegedy [1999]. What are the least tractable instances of max independent set? Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA’1999), 927–928.

    Google Scholar 

  24. O. Kullmann [1997]. Worst-case analysis, 3-SAT decisions, and lower bounds: Approaches for improved SAT algorithms. In: The Satisfiability Problem: Theory and Applications, D. Du, J. Gu, P.M. Pardalos (eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35, 261–313.

    Google Scholar 

  25. O. Kullmann [1999]. New methods for 3-SAT decision and worst case analysis. Theoretical Computer Science 223, 1–72.

    Google Scholar 

  26. E.L. Lawler [1976]. A note on the complexity of the chromatic number problem. Information Processing Letters 5, 66–67.

    Google Scholar 

  27. R.J. Lipton and R.E. Tarjan [1979]. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 177–189.

    Google Scholar 

  28. B. Monien and E. Speckenmeyer [1985]. Solving satisfiability in less than 2n steps. Discrete Applied Mathematics 10, 287–295.

    Google Scholar 

  29. J.W. Moon and L. Moser [1965]. On cliques in graphs. Israel Journal of Mathematics 3, 23–28.

    Google Scholar 

  30. J.M. Nielsen [2001]. Personal communication.

    Google Scholar 

  31. C.H. Papadimitriou [1991]. On selecting a satisfying truth assignment. Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS’1991), 163–169.

    Google Scholar 

  32. C.H. Papadimitriou and M. Yannakakis [1991]. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43, 425–440.

    Google Scholar 

  33. P. Pardalos, F. Rendl, and H. Wolkowicz [1994]. The quadratic assignment problem: A survey and recent developments. In: Proceedings of the DIMACS Workshop on Quadratic Assignment Problems, P. Pardalos and H. Wolkowicz (eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16, 1–42.

    Google Scholar 

  34. R. Paturi, P. Pudlak, and F. Zane [1997]. Satisfiability coding lemma. Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS’1997), 566–574.

    Google Scholar 

  35. R. Paturi, P. Pudlak, M.E. Saks, and F. Zane [1998]. An improved exponential time algorithm for k-SAT. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS’1998), 628–637.

    Google Scholar 

  36. M. Paull and S. Unger [1959]. Minimizing the number of states in incompletely specified sequential switching functions. IRE Transactions on Electronic Computers 8, 356–367.

    Google Scholar 

  37. P. Pudlak [1998]. Satisfiability-algorithms and logic. Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS’1998), Springer, LNCS 1450, 129–141.

    Google Scholar 

  38. J.M. Robson [1986]. Algorithms for maximum independent sets. Journal of Algorithms 7, 425–440.

    Google Scholar 

  39. J.M. Robson [2001]. Finding a maximum independent set in time O(2n/4)? Manuscript.

    Google Scholar 

  40. R. Rodosek [1996]. A new approach on solving 3-satisfiability. Proceedings of the 3rd International Conference on Artificial Intelligence and Symbolic Mathematical Computation Springer, LNCS 1138, 197–212.

    Google Scholar 

  41. I. Schiermeyer [1992]. Solving 3-satisfiability in less than O(1.579n) steps. Selected papers from Computer Science Logic (CSL’1992), Springer, LNCS 702, 379–

    Google Scholar 

  42. I. Schiermeyer [1993]. Deciding 3-colorability in less than O(1.415n) steps. Proceedings of the 19th Workshop on Graph Theoretic Concepts in Computer Science (WG’1993), Springer, LNCS 790, 177–182.

    Google Scholar 

  43. U. Schöning [1999]. A probabilistic algorithm for k-SAT and constraint satisfaction problems. Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS’1999), 410–414.

    Google Scholar 

  44. U. Schöning [2001]. New algorithms for k-SAT based on the local search principle. Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS’2001), Springer, LNCS 2136, 87–95.

    Google Scholar 

  45. R. Schroeppel and A. Shamir [1981]. A T = O(2n/2), S = O(2n/4) algorithm for certain NP-complete problems. SIAM Journal on Computing 10, 456–464.

    Google Scholar 

  46. R.E. Tarjan and A.E. Trojanowski [1977]. Finding a maximum independent set. SIAM Journal on Computing 6, 537–546.

    Google Scholar 

  47. A. van Vliet [1995]. Personal communication.

    Google Scholar 

  48. R. Williams [2002]. Algorithms for quantified Boolean formulas. Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA’2002).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Twente, P.O. Box 217, 7500, AE Enschede, The Netherlands

    Gerhard J. Woeginger

Authors
  1. Gerhard J. Woeginger
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institut für Informatik, Universität zu Köln, Pohligstr. 1, 50969, Köln, Germany

    Michael Jünger

  2. Institut für Informatik, Universität Heidelberg, Im Neuenheimer Feld 368, 69120, Heidelberg, Germany

    Gerhard Reinelt

  3. Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”, CNR, viale Manzoni 30, 00185, Rome, Italy

    Giovanni Rinaldi

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Woeginger, G.J. (2003). Exact Algorithms for NP-Hard Problems: A Survey. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds) Combinatorial Optimization — Eureka, You Shrink!. Lecture Notes in Computer Science, vol 2570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36478-1_17

Download citation

  • DOI: https://doi.org/10.1007/3-540-36478-1_17

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-00580-3

  • Online ISBN: 978-3-540-36478-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics