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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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.
D. Applegate, R. Bixby, V. Chvátal, and W. Cook [1998]. On the solution of travelling salesman problems. Documenta Mathematica 3, 645–656.
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.
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.
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.
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.
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.
R.G. Downey and M.R. Fellows [1999]. Parameterized complexity. Springer Monographs in Computer Science.
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.
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.
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.
U. Feige and J. Kilian [1997]. On limited versus polynomial nondeterminism. Chicago Journal of Theoretical Computer Science (http://cjtcs.cs.uchicago.edu/).
U. Feige and J. Kilian [2000]. Exponential time algorithms for computing the bandwidth of a graph. Manuscript.
M.R. Garey and D.S. Johnson [1979]. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
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.
M. Held and R.M. Karp [1962]. A dynamic programming approach to sequencing problems. Journal of SIAM 10, 196–210.
T. Hofmeister, U. Schöning, R. Schuler, and O. Watanabe [2001]. A probabilistic 3-SAT algorithm further improved. Manuscript.
E. Horowitz and S. Sahni [1974]. Computing partitions with applications to the knapsack problem. Journal of the ACM 21, 277–292.
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.
R. Impagliazzo and R. Paturi [2001]. Complexity of k-SAT. Journal of Computer and System Sciences 62, 367–375.
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.
T. Jian [1986]. An O(20.304n) algorithm for solving maximum independent set problem. IEEE Transactions on Computers 35, 847–851.
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.
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.
O. Kullmann [1999]. New methods for 3-SAT decision and worst case analysis. Theoretical Computer Science 223, 1–72.
E.L. Lawler [1976]. A note on the complexity of the chromatic number problem. Information Processing Letters 5, 66–67.
R.J. Lipton and R.E. Tarjan [1979]. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 177–189.
B. Monien and E. Speckenmeyer [1985]. Solving satisfiability in less than 2n steps. Discrete Applied Mathematics 10, 287–295.
J.W. Moon and L. Moser [1965]. On cliques in graphs. Israel Journal of Mathematics 3, 23–28.
J.M. Nielsen [2001]. Personal communication.
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.
C.H. Papadimitriou and M. Yannakakis [1991]. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43, 425–440.
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.
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.
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.
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.
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.
J.M. Robson [1986]. Algorithms for maximum independent sets. Journal of Algorithms 7, 425–440.
J.M. Robson [2001]. Finding a maximum independent set in time O(2n/4)? Manuscript.
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.
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–
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.
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.
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.
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.
R.E. Tarjan and A.E. Trojanowski [1977]. Finding a maximum independent set. SIAM Journal on Computing 6, 537–546.
A. van Vliet [1995]. Personal communication.
R. Williams [2002]. Algorithms for quantified Boolean formulas. Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA’2002).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights 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