Exact Exponential Algorithms

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.¹⁶

Back to Top

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³⁴ (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.¹⁵

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¹² and Fomin et al.¹⁴ Another classical design technique is dynamic programming,² 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.

Back to Top

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.

MAX-2-SAT. The satisfiability problem takes as input a logical expression built from n variables x₁, x₂, x_n and the Boolean connectives ¬ (NOT), ∨ (OR), and ∧ (AND). The task is to decide whether the expression can be satisfied by assigning a truth value, either 0 (false) or 1 (true), to each variable such that the expression evaluates to 1. For example, the expression

can be satisfied by setting x₁ = 1 and x₂ = 0, whereas the expression

is not satisfiable.

It is customary to assume that the input expression is in conjunctive normal form, where it is required that the expression is the AND of clauses, each of which is an OR of literals, which are variables or negations of variables. If all clauses have k literals, then the expression is in k-conjunctive normal form, or k-CNF. For example, (1) is in 2-CNF and (2) is in 3-CNF. The satisfiability problem for an expression in k-CNF is called the k-CNF satisfiability or k-SAT problem. It is polynomial-time solvable for k ≤ 2 and NP-complete for k ≥ 3.¹⁷

A stronger variant of the problem, maximum k-CNF satisfiability or MAX-k-SAT, gives a threshold t as additional input, and the task is to decide whether there is an assignment of truth values to the variables such that at least t clauses evaluate to 1. This variant is NP-complete for all k ≥ 2.¹⁷

MAX-k-SAT is trivially solvable by trying all possible truth assignments. When a formula has n variables, it has 2ⁿ possible assignments and for each assignment we can compute in polynomial time how many clauses are satisfied. Thus, the total running time, up to a factor polynomial in n, is dominated by 2ⁿ. A special case of the problem, known as MAX-CUT, can be obtained by formulating MAX-2-SAT as a problem of partitioning the vertices of an n-vertex graph into two subsets such that at least t edges cross between subsets. However, even in the special cases of MAX-2-SAT and MAX-CUT, no better algorithm than the trivial exhaustive search was known until the work of Williams.³⁶

Graph Coloring. In the graph coloring problem, we are given as input a graph G with n vertices and a palette of k colors. The task is to decide whether it is possible to assign to each vertex a color from the palette so that the coloring is proper, that is, every edge has distinct colors at its ends. For example, the graph in Figure 1 admits a proper coloring of its vertices using three colors.

The graph coloring problem is polynomial-time solvable for k ≤ 2 and NP-complete for k ≥ 3.¹⁷ The minimum number of colors for which a graph G has a proper coloring is the chromatic number χ(G) of G.

The first algorithmic approaches to compute the chromatic number of a graph can be traced back to the work of Zykov.⁴¹ The idea is based on a branching procedure. The base case of the branching occurs when all pairs of vertices of G are adjacent, that is, G is a complete graph, in which case the chromatic number is equal to the number of vertices in G. Otherwise, G contains a pair u, v of vertices that are not joined by an edge. In every proper coloring of G it holds that u and v either have distinct colors (in which case we construct a new graph by joining u and v with an edge), or have the same color (in which case we construct a new graph by identifying u and v). This enables us to recursively branch on the two cases and return the best of the two solutions obtained. In terms of running time, however, this approach is in general no better than plain exhaustive search, which involves iterating through the kⁿ distinct ways to color the n vertices of G using the k available colors, and for each coloring testing whether it is proper.

After Zykov’s seminal work, the history of algorithms for graph coloring benefits from a digression to the study of independent sets in graphs. In particular, every proper coloring of G has the property that no two vertices of the same color are joined by an edge. Such a set of vertices is an independent set of G. An independent set of G is maximal if it is not a proper subset of a larger independent set of G. In 1976, Lawler²⁷ observed that dynamic programming and advances in the study of independent sets can be used to drastically improve upon the kⁿ exhaustive search. Let us first develop a basic version of the algorithm. Since each color class in a proper coloring of G is an independent set of G, we have that G is k-colorable if and only if the vertex set V of G decomposes into a union of k independent sets of G. Stated in terms of the chromatic number, we have χ(G) = 0 if G has no vertices; otherwise, we have

where (G) is the family of all nonempty independent sets of G, and GI denotes the graph obtained from G by deleting the vertices in I. For every subset X ⊆ V, we can thus compute the chromatic number χ(G[X]) of the subgraph of G induced by X as follows. When X is empty, we set χ(G[X]) = 0. When X is nonempty, we compute the value χ(G[X]) from the already computed values of proper subsets of X by making use of (3).

What is the running time of this algorithm? The algorithm considers all subsets X ⊆ V, and for each such X, it considers all I ⊆ X that are independent in G[X]. The number of such I is at most 2|^X|. Thus, the number of steps of the algorithm is, up to a factor polynomial in n, at most .

Lawler also observed that the basic 3ⁿ-algorithm can be improved. Namely, instead of going through all subsets I ⊆ X that are independent in G[X], it suffices to consider only maximal independent sets of G[X]. It was known²⁹ already in the 1960s that the number of maximal independent sets in a graph with i vertices is at most 3^i/3, and that these sets can be listed in time (3^i/3n). Thus, the exponential part of the running time of the algorithm is bounded by

It is possible to make even further improvements of this idea by more accurate counting of large and small maximal independent sets.¹¹ But in all these improvements the following common pattern seemed unavoidable: we have to go through all vertex subsets of the graph, and for each subset, we have to enumerate an exponential number of subsets, resulting in time Cⁿ, for a constant C > 2.

Hamiltonian Path. In the NP-complete Hamiltonian cycle problem, we are given a graph on n vertices and the task is to decide whether the graph has a Hamiltonian cycle, which is a cycle visiting every vertex of the graph exactly once. For example, the graph in Figure 2 has a Hamiltonian cycle, outlined in bold edges.

This is a special case of the famous Traveling Salesman Problem, where the task is to, given an n × n matrix of travel costs between n cities, design a travel schedule that visits each city exactly once and returns back to the starting point so that the total cost is minimized.

A stronger variant, the Hamiltonian path problem, constrains one of the vertices as the first vertex s and another vertex t as the last vertex, and asks us to decide whether the graph has a path that starts at s, ends at t, and visits all the vertices exactly once. (By trying all the pairs {s, t} joined by an edge, we can solve the Hamiltonian cycle problem if we can solve the Hamiltonian path problem.)

For the Hamiltonian path problem, exhaustive search iterates through the (n − 2)! ways to arrange the n vertices into a sequence that starts at s and ends at t, testing for each sequence whether it forms a path (of the minimum cost).

Bellman³ and Held and Karp¹⁹ used dynamic programming to solve the problem in time (2ⁿn²), by keeping track for every vertex v and vertex subset S, the existence (or the minimum cost) of a path from s to v that visits exactly the vertices in S ⊆ V. This algorithm, however, requires also space 2ⁿ.

It is possible to solve the problem within the same running time but within polynomial space by making use of the principle of inclusion and exclusion. It seems that essentially the same approach was rediscovered several times.^1,23,25 To illustrate the design, Figure 3 displays a graph with n = 8 vertices {a, b, c, d, e, f, g, h}.

Let us assume that s = a and t = h. A walk of length n − 1 that starts from s and ends at t can be viewed as a string of length 2n − 1 with alternating and possibly repeating vertices and edges, such as

or

We observe that each such walk makes exactly n visits to vertices and contains, possibly with repetitions, n − 1 edges. Moreover, the walk is a Hamiltonian path if and only if the walk visits n distinct vertices; indeed, otherwise there is at least one vertex that is visited more than once. For example, (4) is a path and (5) is a non-path because it repeatedly visits f (and c).

Although finding a Hamiltonian path is a challenging computational problem, one can compute in polynomial time the number of walks of length k from s to t. Indeed, let A be the adjacency matrix of G with rows and columns indexed by vertices of G, such that the (x, y)-entry of A is set to 1 if there is an edge from x to y in G, and set to 0 otherwise. By induction on k we observe that the (s, t)-entry of the kth matrix power A^k counts the number of walks of length k in G that start at s and end at t. Therefore, the number of walks of length n − 1 can be read from the matrix Aⁿ⁻¹, which can be computed in time polynomial in n.

One approach to isolate the paths among the walks is to employ the principle of inclusion and exclusion. Consider a finite set X and three subsets A₁, A₂, and A₃ (see Figure 4).

To obtain |A₁ ∪ A₂ ∪ A₃|, we can use the following formula

or, equivalently,

The principle of inclusion and exclusion generalizes the last formula to the case when there are q subsets A₁, A₂, …, A_q of X by

Let us come back to the Hamiltonian path problem. Take q = n − 2 and suppose that the vertices other than s and t are labeled with integers 1, 2, …, n − 2. Let X be the set of all walks of length n − 1 from s to t and, for each i = 1, 2, …, n − 2, let A_i be the set of walks in X that avoid the vertex i. Then, X is the set of Hamiltonian paths, and we can use (6) to count their number. In particular, for each fixed J ⊆ {1, 2, …, q}, the right-hand side of (6) can be computed time polynomial in n by counting the number of walks of length n − 1 from s to t in the graph with the vertices in J deleted.

This approach can be used to compute the number of Hamiltonian paths in an n-vertex graph in time (2ⁿn). It is also possible to obtain similar running time by making use of dynamic programming. But in both approaches, it seemed that the most time consuming part of the procedure, going through all possible vertex subsets, was unavoidable. This situation was particularly frustrating because the 2ⁿ barrier had withstood attacks since the early 1960s.

Back to Top

Surprise 1: MAX-2-SAT

Let us recall that for MAX-2-SAT the challenge was to break the 2ⁿ barrier in running time. The following approach for doing this is due to Williams.³⁶ An alternative approach via sum-product algorithms is due to Koivisto.²⁶

Let us start with a seemingly unrelated task, namely that of deciding whether a given directed graph D contains a triangle, that is, a triple x, y, z of vertices such that the arcs xy, yz, and zx occur in D. While the immediate combinatorial approach to find a triangle in a v-vertex graph is to try all possible triples of vertices, which would require (v³) steps, there is a faster algorithm of Itai and Rodeh.²² The algorithm relies on formulating the problem in terms of linear algebra. Let A be the adjacency matrix of D, and recall that the (s, t)-entry of the kth power A^k counts the number of walks of length k from s to t. In particular, every walk of length 3 that starts and ends at a vertex x must pass through three distinct vertices, and thus form a triangle, enabling us to extract the number of triangles in D from the diagonal entries of the matrix A³. Thus, it suffices to compute the matrix A³. The immediate algorithm for computing the product of two v × v matrices requires (v³) steps. However, this product can be computed in time (v^ω), where ω < 2.376 is the so-called square matrix multiplication exponent; see Coppersmith and Winograd⁷ and Strassen.³² Very recently, it has been shown that ω < 2.3727.³³

The key insight is now to exploit the fact that triangles can be found quickly to arrive at a nontrivial algorithm for MAX-2-SAT. Toward this end, suppose we are given as input a 2-CNF formula F over n variables. We may assume that n is divisible by 3 by inserting dummy variables as necessary. Let X be the set of variables of F and let X₀, X₁, X₂ be an arbitrary partition of X into sets of size n/3.

Let us transform the instance F into a directed graph D as follows. For every i = 0, 1, 2 and every subset T_i ⊆ X_i, the graph D has a vertex T_i. The meaning of T_i is that it corresponds to an assignment that sets all variables in T_i to the value 1 and all variables in X_iT_i to the value 0. Let us write V_i for the set of all subsets T_i ⊆ X_i. The arcs of D are all possible pairs of the form (T_i, T_j), where T_i ⊆ X_i, T_j ⊆ X_j, and j ≡ i + 1 (mod 3). We observe that D has v = 3 × 2^n/3 vertices and 3 × 2^2n/3 arcs. For i = 0, 1, 2, let the set C_i consist of all clauses of F that either (a) contain variables only from X_i; or (b) contain one variable from X_i and one variable from X_j, with j ≡ i + 1 (mod 3). Now observe that every clause of F has at most two variables. In particular, either both these variables belong to some set X_i, or one variable is in X_i and the other is in X_j with j ≡ i + 1 (mod 3). Thus, the sets C₀, C₁, C₂ partition the clauses in F. We still require weights on the arcs of D. Let us set the weight w(T_i, T_j) of the arc from T_i ⊆ X_i to T_j ⊆ X_j to be equal to the number of clauses in C_i satisfied by assigning the value 1 to all variables in T_i ∪ T_j and the value 0 to all remaining variables in (X_i ∪ X_j) (T_i ∪ T_j).

To illustrate the construction, let us assume F is the following formula

and partition the variables so that X₀ = {x₁, x₂}, X₁ = {x₃, x₄}, and X₂ = {x₅, x₆}. Then, C₀ = {(x₁ ∨ x₂), (¬x₂ ∨ x₃), (x₁ ∨ x₃), (¬x₂ ∨ x₄)}, C₁ = {(x₃ ∨ x₄), (¬x₄ ∨ ¬x₆)}, and C₂ = {(x₁ ∨ ¬ x₅)}. Figure 5 illustrates the underlying graph D, where each set V₀, V₁, V₂ has size 4. For example, V₀ = {Ø, {x₁}, {x₂}, {x₁, x₂}}. For sets T₀ = Ø, T₁ = {x₃, x₄}, and T₂ = {x₆}, the corresponding assignment, viz. x₁ = x₂ = 0, x₃ = 1, x₄ = 1, x₅ = 0, x₆ = 1, satisfies five clauses. Accordingly, the weight of the triangle T₀T₁T₂ in D is also five.

The equivalence of the following statements follows from the construction of D: (i) There is a subset of variables T ⊆ X such that exactly t clauses are satisfied by assigning the value 1 to variables in T and the value 0 to the variables in XT. (ii) The graph D contains a triangle T₀T₁T₂ with T_i ⊆ X_i for each i = 0, 1, 2 such that

Thus, to find an assignment that satisfies most clauses, it suffices to find a heaviest triangle in D.

We are almost done. Indeed, every formula with n variables has at most 4n² clauses of length 2, and hence to find a heaviest triangle, it suffices to test for the existence of a triangle of weight t for each 0 ≤ t ≤ 4n² in turn. To test for a triangle of weight t, we go through all possible (t³) partitions t = t₀ + t₁ + t₂ into nonnegative parts, and for each partition, we construct a subgraph of D by leaving only arcs of weight t_i for arcs going from subsets of X_i to subsets of X_j with j ≡ i + 1 (mod 3). Finally, it suffices to decide whether has a triangle. The subgraph can be constructed in time (2^2n/3n) by going through all arcs of D. The total running time is thus

Because ω < 2.376, we conclude that the running time of the algorithm is (1.74ⁿ).

Back to Top

Surprise 2: Graph Coloring

The next surprise is due to Björklund et al.⁶ To explain the idea of the algorithm, it will again be convenient to start with a task that may appear at first completely unrelated, namely the multiplication of polynomials. To multiply two given polynomials, the elementary algorithm is to cross-multiply the monomials pairwise and then collect to obtain the result:

In particular, if we are multiplying two polynomials of degree d (that is, the highest degree of a monomial with a nonzero coefficient is d), we require (d²) steps to get the result via the elementary algorithm due to the cross-multiplication of monomials. Fortunately, we can drastically improve upon the elementary algorithm by deploying the fast Fourier transform (FFT) to evaluate both input polynomials (given as two lists of d + 1 coefficients, one coefficient for each monomial) at 2d + 1 distinct points, x₀, x₁, x_2d, then multiplying the evaluations pointwise, and finally employing the inverse FFT to recover the list of coefficients for the product polynomial. With such an algorithm, the number of operations is reduced from (d²) to (d log d).

But what about graph coloring? Could we formulate the task of decomposing the vertex set into a union of independent sets of G as a task analogous to polynomial multiplication? Let us try to find the solution incrementally for j = 1, 2, …, k. Suppose we have a list of all the sets of vertices that decompose into a union of j independent sets of G, and would like to determine such a list for j + 1.

Let us consider an example. Figure 6 displays a graph with n = 4 whose independent sets are

For j = 2, the sets of vertices that decompose into a union of j independent sets are

Given the family of independent sets and the family of solutions for j, we would like to determine the family of solution for j + 1. Pursuing an analogy with polynomial multiplication, we can view the sets in both set families as “monomials” and multiply these “monomials” using set union. For example:

In general, both set families being multiplied may have up to 2ⁿ members, and the same holds for the product. Again the elementary algorithm will consider the monomials pairwise, which requires consideration of 2ⁿ × 2ⁿ = 4ⁿ pairs in the worst case. But analogous to polynomial multiplication, it turns out that we can do considerably better.

Suppose the input set families are f and g. We can view f (and similarly g) as a function that takes an integer value f(S) for each subset S ⊆ V of our n-element vertex set V. (Indeed, let us assume that we have f(S) = 1 if and only if the set S is in the family, and f(S) = 0 otherwise.) The product, e = f ∪ g, is then a similar function defined for each S ⊆ V by the rule

Since each pair (A, B) contributes by f(A) g(B) to the value of e at exactly S = A ∪ B, we observe that (4ⁿ) multiplications and additions suffice to compute the function e from the given functions f and g, which corresponds to the elementary multiplication algorithm. Now, the analogy to the FFT algorithm for multiplying polynomials suggests a different approach, namely to transform the inputs f and g somehow, then multiply pointwise, and finally transform back to the original representation to recover f ∪ g. The relevant transform turns out to be the zeta transform fζ of f, defined for all Y ⊆ V by

and its inverse, the Möbius transform fμ of f, defined for all Y ⊆ V by

Indeed, the product f ∪ g can be computed using the expression

Both the zeta transform f fζ and the Möbius transform f fμ admit fast algorithms analogous to the FFT. Indeed, it follows from the work of Yates⁴⁰ (see Knuth²⁴) that given f as input, we can compute fζ (and similarly fμ) using (2ⁿn) additions and subtractions. This algorithm is perhaps best illustrated in arithmetic circuit form, which Figure 7 illustrates in the case n = 3. Observe that each of the n dashed cubes takes the sum along one of the n “dimensions” so that each output fζ(Y) ends up taking the sum of all the inputs f(X) with X ⊆ Y.

We can thus compute e = f ∪ g from f and g given as input using (2ⁿn) additions, negations, and multiplications.

It now follows that we can decide in (2ⁿnk) steps whether a given n-vertex graph G is k-colorable. Indeed, we first compute the characteristic function f of the independent sets of G, that is, for each S ⊆ V we set f(S) = 1 if S is independent in G, and f(S) = 0 otherwise. Next, we compute the functions e_j for j = 1, 2, …, k by starting with e₁ = f and taking the product e_j = f ∪ e_j−1 for j ≥ 2. We have that G is k-colorable if and only if e_k(V) > 0.

Back to Top

Surprise 3: Hamiltonian Path

Here we illustrate the third surprise, namely a randomized algorithm for the Hamiltonian path problem that runs in time (1.66ⁿ). This algorithm is due to Björklund.⁴ For ease of exposition, we restrict our consideration to bipartite graphs and obtain running time (1.42ⁿ). (The algorithm design here is also slightly different from Björklund’s original design; here we rely on reversal of a closed subwalk for cancellation of non-paths⁵ and, inspired by Cygan et al.,⁸ use the Isolation Lemma in place of polynomial identity testing.)

Let us return to the example in Figure 3. We observe that the graph is bipartite with n = 8, V₁ = {a, b, c, d}, and V₂ = {e, f, g, h}. As before, our task is to decide whether there exists a Hamiltonian path from vertex s to vertex t. Let us assume that s = a and t = h.

Every walk of length n − 1 makes exactly n visits to vertices, where exactly n/2 visits are to vertices in V₁ because the graph is bipartite. Let us now label each of the n/2 visits to V₁ using an integer from L = {1, 2, …, n/2}. In particular, each walk has (n/2)^n/2 possible labelings, exactly (n/2)! of which are bijective, that is, each label is used exactly once. For example, let us consider the labeled walk

We observe that (7) is a bijectively labeled non-path.

Let us now partition the set of all labeled walks into two disjoint classes, the “good” class and the “bad” class. A labeled walk is good if the labeling is bijective and the walk is a path. Otherwise a labeled walk is bad. We observe that the good class is nonempty if and only if the graph has a Hamiltonian path from s to t.

We now develop a randomized algorithm that decides whether the good class is nonempty. The key idea is to build a sieve for filtering labeled walks so that (a) the bad class is always filtered out and (b) a “witness” from the good class remains with fair probability whenever the good class is nonempty. Conceptually, it will be convenient to regard the sieve as a “bag” (multiset) to which we “hash” labeled walks so that upon termination each “bad” hash value will occur in the bag an even number of times, and each “good” hash value will occur exactly once.

Define the hash of a labeled walk to be the multiset that consists of all the elements visited by a walk, together with their labels (if any). For example, the hash value of (7) is

In general, we cannot reconstruct a labeled walk from its hash value. However, every bijectively labeled path—that is, every good labeled walk—can be reconstructed from its hash value. Indeed, the vertices in a path are distinct, and the set of edges of a path determines the ordering of the vertices, which we know must start with s and end with t. Thus, each good labeled walk has a unique hash value.

Our next objective is to make sure that each hash value arising from a bad labeled walk gets inserted an even number of times into the sieve. Toward this end, there are two disjoint types of bad labeled walks, namely (a) bijectively labeled non-paths and (b) non-bijectively labeled walks.

Let us consider a bijectively labeled non-path W. We show that W can be paired with a bijectively labeled non-path W′ with the same hash value. If we view W as a string, there is a minimal string prefix that contains a repeated vertex. Let us call the last vertex v in such a prefix the first repeated vertex in W. Let v be the first repeated vertex in W, and call the subwalk between the first two occurrences of v in W the first closed subwalk in W. For example, in (7) the first closed subwalk is . There are two cases to consider in setting up the pairing, depending on whether the first repeated vertex in W is in V₁ or in V₂.

If the first repeated vertex is in V₁, let us define W’ by transposing the labels of the first and last vertex in the first closed subwalk (that is, the first two occurrences of the first repeated vertex in W). For example, in the case of (7) we obtain

Clearly, W and W’ have the same hash value. Furthermore, because W is bijectively labeled, W′ ≠ W. Since W″ = W, we have a bijective pairing of bijectively labeled non-walks where the first repeated vertex is in V₁.

If the first repeated vertex is in V₂, let us reverse the first closed subwalk (also reversing the labels) in W to obtain the bijectively labeled non-path W′. For example,

gets paired with

It is immediate that W and W’ have the same hash value. We also observe that W” = W since two reversals restore the original bijectively labeled non-path. It remains to conclude that W ≠ W’. Here it is not immediate that reversing the first closed subwalk will result in a different labeled walk. Indeed, the first closed subwalk may be a palindrome, such as in

Fortunately, because of bijective labeling, the only possible pitfall is a palindrome of length 5 that starts at V₂, visits a vertex in V₁, and returns to the same vertex in V₂. We can avoid such palindromes by keeping track of the last vertices visited by a partial walk, and hence assume that our labeled walks do not contain such palindromes, and consequently W’ ≠ W. Thus, the set of bijectively labeled non-paths partitions into disjoint pairs {W, W’}, where each pair has the same hash value.

Next, let us consider a non-bijectively labeled walk W. Each such W avoids at least one label from the set of all labels L. In particular, if W avoids exactly a labels, there are exactly 2^a sets A ⊆ L such that W avoids every label in A (and possibly some other labels outside A).

From the previous observations we now obtain the following high-level algorithm. For each subset A ⊆ L in turn, we insert into the sieve the hash value of each labeled walk that avoids every label in A. After all subsets A have been considered, a hash value occurs with odd multiplicity in the sieve if and only if it originates from a good labeled walk.

A second key idea is now to implement the sieve at low level using what is essentially a layer of hashing so that the hash values—such as (8)—are not considered explicitly, but rather by weight only. That is, instead of sieving hash values explicitly, we sieve only their weights. In particular, at the start of the algorithm, let us associate an integer weight in the interval 1, 2, …, n(n+1) independently and uniformly at random to each of the (n+1)n/2 elements that may occur in a hash value. The weight of a hash value is the sum of the weights of its elements. When running the sieve, instead of tracking the (partial) walks and their (partial) hash values by dynamic programming, we only track the number of hash values of each weight. This enables us to process each fixed A ⊆ L in time polynomial in n. The number of all sets A ⊆ L is 2^|L| ≤ 2^n/2 < 1.42ⁿ. Thus, the total running time of the above procedure is (1.42ⁿ). When the sieve terminates, we assert that the input graph has a Hamiltonian path if the counter for the number of hash values of at least one weight is odd; otherwise we assert that the graph has no Hamiltonian path.

To see that the presence of an odd counter implies the existence of a Hamiltonian path, observe that by our careful design, each bad hash value gets inserted into the sieve an even number of times, and in particular contributes an even increment to the counter corresponding to the weight of the hash value. Thus, an odd counter can arise only if a good hash value was inserted into the sieve, that is, the graph has a Hamiltonian path.

Next, let us study the probability of a false negative, that is, all counters are even although the graph has a Hamiltonian path. Here it suffices to invoke the “Isolation Lemma” of Mulmuley et al.³⁰ which states that for any set family over a base set of m elements, if we assign a weight independently and uniformly at random from 1, 2, …, r to each element of the base set, there will be a unique set of the minimum weight in the family with probability at least 1 − m/r. In particular, if we consider the set family of good hash values—indeed, each good hash value is a set—there is a unique such hash value of the minimum weight—and hence an odd counter in the sieve—with probability at least 1/2.

We thus have a randomized algorithm for detecting Hamiltonian paths in bipartite graphs that runs in time (1.42ⁿ), gives no false positives, and gives a false negative with probability at most 1/2. (The algorithm could now be extended to graphs that are not bipartite with running time (1.66ⁿ) by partitioning the vertices randomly into V₁ and V₂ and employing a bijective labeling also for the edges with both ends in V₂.)

Back to Top

Conclusion

This article has highlighted three recent results in exact exponential algorithms, with the aim of illustrating the range of techniques that can be employed and the element of surprise in each case. In this regard, it is perhaps safe to say that the area is still in a state of flux, and with more research one can expect more positive surprises. Certainly, the authors do not mind to be labeled as optimists in this sense. We also hope the three highlighted results have illustrated perhaps the main reason why one wants to study algorithms that run in exponential time. That is, the study of exponential time algorithms is really a quest for understanding computation and the structure of computational problems, including pursuing the sometimes surprising connections uncovered in such a quest.

We conclude with three challenge problems, each of which at first sight appears quite similar to one of the three surprises we have covered in this article. Frustratingly enough, however, there has been no progress at all on these problems.

MAX-3-SAT. We have seen that MAX-2-SAT can be solved in time (2^ωn/3) essentially because of the existence of nontrivial algorithms for matrix multiplication. But no such tools are available when one considers instances with clauses of length 3 instead of length 2. The challenge is to find an algorithm that runs in time ((2 − ε)ⁿ) for MAX-3-SAT, where n is the number of variables and ε > 0 is a constant independent of n.

Edge Coloring. The edge-coloring problem asks us to color the edges of a graph using the minimum number of colors such that the coloring is proper, that is, any two edges that share an endvertex must receive different colors. It is known that the number of colors required is either Δ or Δ + 1, where Δ is the maximum degree of a vertex, and it is NP-complete to decide which of the two cases occurs.²⁰ For a graph G, the edge-coloring of G is equivalent to deciding whether the chromatic number of the line graph L(G) of G is Δ or Δ + 1, which implies that edge-coloring can be solved in time 2^mm ⁽¹⁾, where m is the number of edges in G. The challenge is to find an algorithm that runs in time ((2 − ε)^m) where ε > 0 is independent of m.

Traveling Salesman. While the Hamiltonian cycle problem can be solved in randomized time (1.66ⁿ), no such algorithm is known for the Traveling Salesman Problem with n cities and travel costs between cities that are nonnegative integers whose binary representation is bounded in length by a polynomial in n. The challenge is to find an algorithm that runs in time ((2 − ε)ⁿ) where ε > 0 is independent of n.

Back to Top

Further Reading

Beyond the highlighted results in this article, the recent book of Fomin and Kratsch¹⁵ and the surveys of Woeginger^38,39 provide a more in-depth introduction to exact exponential algorithms. Dantsin and Hirsch⁹ survey algorithms for SAT, while Malik and Zhang²⁸ discuss the deployment of SAT solvers in practical applications. Husfeldt²¹ gives an introduction to applications of the principle of inclusion and exclusion in algorithmics. Flum and Grohe¹³ give an introduction to parameterized complexity theory and its connections to subexponential and exponential time complexity. Williams³⁷ relates improvements to exhaustive search with superpolynomial lower bounds in circuit complexity.

Back to Top

Acknowledgments

The authors would like to thank Andreas Björklund, Thore Husfeldt, Mikko Koivisto, and Dieter Kratsch for their comments that greatly helped to improve the exposition in this review. F.V.F. acknowledges the support of the European Research Council (ERC), grant Rigorous Theory of Preprocessing, reference 267959. P.K. acknowledges the support of the Academy of Finland, Grants 252083 and 256287.

Back to Top

Back to Top

Back to Top

Back to top