2013 ExactExponentialAlgorithms

(Fomin & Kaski, 2013) ⇒ Fedor V. Fomin, and Petteri Kaski. (2013). “Exact Exponential Algorithms.” In: Communications of the ACM Journal, 56(3). doi:10.1145/2428556.2428575

Subject Headings: Exact Exponential Algorithm; Maximum 2-Satisfiability; Graph Coloring; Hamiltonian Path.

Notes

Cited By

Quotes

Abstract

Discovering surprises in the face of intractability.

Introduction

Many computational problems have been shown to be intractable, either in the strong sense that no algorithm exists at all — the canonical example being the undecidability of the Halting Problem — or that no efficient algorithm exists. From a theoretical perspective perhaps the most intriguing case occurs with the family of NP-complete problems, for which it is not known whether the problems are intractable. That is, despite extensive research, neither is an efficient algorithm known, nor has the existence of one been rigorously ruled out.[16]

To cope with intractability, advanced techniques such as parameterized algorithms [10,13,31] (that isolate the exponential complexity to a specific structural parameter of a problem instance) and approximation algorithms [34] (that produce a solution whose value is guaranteed to be within a known factor of the value of an optimum solution) have been developed. But what can we say about finding exact solutions of non-parameterized instances of intractable problems? At first glance, the general case of an NP-complete problem is a formidable opponent: when faced with a problem whose instances can express arbitrary nondeterministic computation, how is one to proceed at solving a given instance, apart from the obvious exhaustive search that "tries out all the possibilities"?

Fortunately, the study of algorithms knows many positive surprises. Computation is malleable in nontrivial ways, and subtle algorithmically exploitable structure has been discovered where none was thought to exist. Furthermore, the more generous a time budget the algorithm designer has, the more techniques become available. Especially so if the budget is exponential in the size of the input. Thus, absent complexity-theoretic obstacles, one should be able to do better than exhaustive search. This is the objective of exact exponential algorithms.[15]

Arguably, the oldest design technique to improve upon exhaustive search is branching or backtrack search,[18,35] which recursively splits the exhaustive search space, attempting to infer in the process that parts of the space need not be visited. For recent applications of branching techniques, we refer to Eppstein[12] and Fomin et al.[14] Another classical design technique is dynamic programming,[2] which derives a solution from the bottom up by storing solutions of smaller subproblems and combining them via a recurrence relation to progressively yield solutions of larger subproblems. These two techniques in many cases give significant improvements over plain exhaustive search, but in other cases, no improvement at all upon exhaustive search has been available, and many problems remain with this status.

In what follows, we do not try to give a comprehensive survey of exact exponential algorithms. Indeed, even listing the most significant results would require a format different from this review. Instead, we have chosen to review the area by highlighting three recent results. In each case, research had been essentially stuck for an extended period of time — in one case for almost 50 years! — and it was conceivable that perhaps no improvement could be obtained over the known algorithms. But computation has the power to surprise, and in this article we hope to convey some of the excitement surrounding each result. We also find these results particularly appealing because they are a posteriori quite accessible compared with many of the deep results in theoretical computer science, and yet they illustrate the subtle ways in which computation can be orchestrated to solve a problem.

…

Three NP-Complete Problems

The three problems we discuss in more detail are Maximum 2-Satisfiability, Graph Coloring, and Hamiltonian Path. We start by giving an overview of previous approaches to attack each problem, and then in the subsequent sections discuss the novel algorithms.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 ExactExponentialAlgorithms	Fedor V. Fomin Petteri Kaski			Exact Exponential Algorithms				10.1145/2428556.2428575