IntroductionTechnical PreliminariesTechnique: Dynamic Programming across the SubsetsTechnique: Pruning the Search TreeTechnique: Preprocessing the DataTechnique: Local SearchHow Can We Prove That a Problem Has No Sub-exponential Time Exact Algorithm?Concluding RemarksExact Algorithms for NP-Hard Problems:A SurveyGerhard J. WoegingerDepartment of MathematicsUniversity of Twente, P.O. Box 2177500 AE Enschede, The NetherlandsAbstract. We discuss fast exponential time solutions for NP-completeproblems. We survey known results and approaches, we provide pointersto the literature, and we discuss several open problems in this area. Thelist of discussed NP-complete problems includes the travelling salesmanproblem, scheduling under precedence constraints, satisfiability, knap-sack, graph coloring, independent sets in graphs, bandwidth of a graph,and many more.1 IntroductionEvery NP-complete problem can be solved by exhaustive search. Unfortunately,when the size of the instances grows the running time for exhaustive searchsoon becomes forbiddingly large, even for instances of fairly small size. For someproblems it is possible to design algorithms that are significantly faster thanexhaustive search, though still not polynomial time. This survey deals with suchfast, super-polynomial time algorithms that solve NP-complete problems to opti-mality. In recent years there has been growing interest in the design and analysisof such super-polynomial time algorithms. This interest has many causes.– It is now commonly believed that P=NP, and that super-polynomial timealgorithms are the best we can hope for when we are dealing with an NP-complete problem. There is a handful of isolated results scattered across theliterature, but we are far from developing a general theory. In fact, we havenot even started a systematic investigation of the worst case behavior of suchsuper-polynomial time algorithms.– Some NP-complete problems have better and faster exact algorithms thanothers. There is a wide variation in the worst case complexities of knownexact (super-polynomial time) algorithms. Classical complexity theory cannot explain these differences. Do there exist any relationships among theworst case behaviors of various problems? Is progress on the different prob-lems connected? Can we somehow classify NP-complete problems to see howclose we are to the best possible algorithms?– With the increased speed of modern computers, large instances of NP-complete problems can be solved effectively. For example it is nowadaysroutine to solve travelling salesman (TSP) instances with up to 2000 cities.M. J¨unger et al. (Eds.): Combinatorial Optimization (Edmonds Festschrift), LNCS 2570, pp. 185–207, 2003.cSpringer-Verlag Berlin Heidelberg 2003186 G.J. WoegingerAnd if the data is nicely structured, then instances with up to 13000 citiescan be handled in practice (Applegate, Bixby, Chv´atal & Cook [2]). There isa huge gap between the empirical results from testing implementations andthe known theoretical results on exact algorithms.– Fast algorithms with exponential running times may actually lead to practi-cal algorithms, at least for moderate instance sizes. For small instances, analgorithm with an exponential time complexity of O(1.01n) should usuallyrun much faster than an algorithm with a polynomial time complexity ofO(n4).In this article we survey known results and approaches to the worst case analysisof exact algorithms for NP-hard problems, and we provide pointers to the liter-ature. Throughout the survey, we will also formulate many exercises and openproblems. Open problems refer to unsolved research problems, while exercisespose smaller questions and puzzles that should be fairly easy to solve.Organization of this survey. Section 2 collects some technical preliminaries andsome basic definitions that will be used in this article. Sections 3–6 introduce andexplain the four main techniques for designing fast exact algorithms: Section 3deals with dynamic programming across the subsets, Section 4 discusses pruningof search trees, Section 5 illustrates the power of preprocessing the data, andSection 6 considers approaches based on local search. Section 7 discusses methodsfor proving negative results on the worst case behavior of exact algorithms.Section 8 gives some concluding remarks.2 Technical PreliminariesHow do we measure the quality of an exact algorithm for an NP-hard problem?Exact algorithms for NP-complete problems are sometimes hard to compare,since their analysis is done in terms of different parameters. For instance, foran optimization problem on graphs the analysis could be done in terms of thenumber n of vertices, or possibly in the number m of edges. Since the standardreductions between NP-complete problems may increase the instance sizes, manyquestions in computational complexity theory depend delicately on the choiceof parameters. The right approach seems to be to include an explicit complexityparameter in the problem specification (Impagliazzo, Paturi & Zane [21]). Re-call that the decision version of every problem in NP can be formulated in thefollowing way:Given x, decide whether there exists y so that |y|≤m(x) and R(x, y).Here x is an instance of the problem; y is a short YES-certificate for this instance;R(x, y) is a polynomial time decidable relation that verifies certificate y forinstance x; and m(x) is a polynomial time computable and polynomially boundedcomplexity parameter that bounds the length of the certificate y. A trivial exactalgorithm for solving x would be to enumerate all possible strings with lengthsExact Algorithms for NP-Hard Problems: A Survey 187up to m(x), and to check whether any of them yields a YES-certificate. Up topolynomial factors that depend on the evaluation time of R(x, y), this wouldyield a running time of 2m(x). The first goal in exact algorithms always is tobreak the triviality barrier, and to improve on the time complexity of this trivialenumerative algorithm.Throughout this survey, we will measure the running times of algorithmsonly with respect to the complexity parameter m(x). We will use a modifiedbig-Oh notation that suppresses all other (polynomially bounded) terms thatdepend on the instance x and the relation R(x, y). We write O∗(T (m(x))) for atime complexity of the form O(T (m(x)) · poly(|x|)). This modification may bejustified by the exponential growth of T (m(x)). Note that for instance for simplegraphs with
View Full Document
Unlocking...