Wouldn’t the sentence “I want to put a hyphen between the words Fish and And and And andChips in my Fish-And-Chips sign.” have been clearer if quotation marks had been placed
before Fish, and between Fish and and, and and and And, and And and and, and and andAnd, and And and and, and and and Chips, as well as after Chips?1— Martin Gardner, Aha! Insight (1978)
BMO: I ﬁnished with my computations! As I thought, it’s a real language they are speaking
based on intonations! [speaking to Chips and Ice Cream] Chips? Chips chips chips!
Ice cream?
Chips: Chips chips chips!
Ice Cream: Ice cream ice cream!
— “Chips and Ice Cream”, Adventure Time season 6, episode 34 (April 30, 2015)
For every polynomial-time algorithm you have,there is an exponential algorithm that I would rather run.
— Alan Perlis (ﬁrst Turing Award winner)

B
Faster Exponential Algorithms[Read Chapters 2, 3, and 12 ﬁrst.]
Status: Unﬁnished.

There are many useful problems—including but not limited to the set of all NP-hardproblems—for which the fastest algorithm known runs in exponential time. Moreover,there is very strong evidence (but alas, no proof) that it is impossible to solve these
problems in less than exponential time—it’s not that we’re all stupid; the problems really
are that hard!
But sometimes we have to solve these problems anyway. In these circumstances, it isimportant to ask: Which exponential? An algorithm that runs in O(2n ) time, while still0

If you ever decide to read this sentence out loud, be sure to pause briefly between ‘Fish and and’ and‘and and and And’, ‘and and and And’ and ‘and And and and’, ‘and And and and’ and ‘and and and And’,‘and and and And’ and ‘and And and and’, and ‘and And and and’ and ‘and and and Chips’!
Did you notice the punctuation I carefully inserted between ‘Fish and and’ and ‘and’, ’and’ and ’and andand And’, ‘and and and And’ and ’and and and And’, ‘and and and And’ and ’and’, ’and’ and ‘and And andand’, ‘and And and and’ and ‘and And and and’, ‘and And and and’ and ’and’, ’and’ and ‘and and and And’,‘and and and And’ and ‘and and and And’, ‘and and and And’ and ‘and’, ‘and’ and ‘and And and and’, ‘andAnd and and’ and ‘and’, ‘and’ and ‘and And and and’, ‘and And and and’ and ‘and’, and ‘and’ and ‘and andand Chips’?

© 2018 Jeff Erickson

http://algorithms.wtf

1

B. FASTER EXPONENTIAL ALGORITHMS

unusable for large instances, is still significantly better than an algorithm that runs inO(4n ) time; an algorithm that runs in O(1.5n ) or O(1.25n ) is better still.
The most straightforward method to find an optimal solution to an NP-hard problem torecursively generate all possible solutions via recursive backtracking and check each one:all satisfying assignments, or all vertex colorings, or all subsets, or all permutations, orwhatever. However, many (perhaps even most) NP-hard problems have some additional
structure that allows us to prune away most of the branches of the recursion tree, thereby
drastically reducing the running time.

B.1 3SAT
Let’s consider the mother of all NP-hard problems: 3Sat. Given a boolean formulain conjunctive normal form, with at most three literals in each clause, our task is todetermine whether any assignment of values of the variables makes the formula true. Yes,
this problem is NP-hard, which means that a polynomial algorithm is almost certainly
impossible. Too bad; we have to solve the problem anyway.
The trivial solution is to try every possible assignment. We’ll evaluate the running
time of our 3Sat algorithms in terms of two variables: n is the number of variables in the
input formula, and m is the number of clauses. There are 2n possible assignments, andwe can evaluate each assignment in O(m) time, so the overall running time is O(2n m).
Assuming no clause appears in the input formula more than once—a condition that we
can easily enforce in polynomial time—then m = O(n3 ), so the running time is at mostO(2n n3 ).
Polynomial factors like n3 are essentially noise when the overall running time isexponential, so from now on I’ll write poly(n) to represent any polynomial function of n;
in other words, poly(n) := nO(1) . For example, the trivial algorithm for 3Sat runs in timeO(2n poly(n)).

One Clause
Recall that all 3CNF formulas have the following recursive structure
A 3CNF formula is either nothingor (a clause with three literals) ∧ (a 3CNF formula)
Suppose we want to decide whether some 3CNF formula Φ with n variables is satisfiable.
Of course this is trivial if Φ is the empty formula, so suppose
Φ = (x ∨ y ∨ z) ∧ Φ0for some literals x, y, z and some 3CNF formula Φ0 . By distributing the ∧ across the ∨s,
we can rewrite Φ as follows:Φ = (x ∧ Φ0 ) ∨ ( y ∧ Φ0 ) ∨ (z ∧ Φ0 )2

B.1. 3SATFor any boolean formula Ψ and any literal x, let Ψ|x (pronounced “sigh given eks")denote the simpler boolean formula obtained by setting x to True and simplifying as
much as possible. If Ψ has n variables, then Ψ|x has at most n − 1 variables.
It’s not hard to prove by induction (hint, hint) that x ∧ Ψ = x ∧ (Ψ|x), and thereforeΦ = (x ∧ (Φ0 |x)) ∨ ( y ∧ (Φ0 | y)) ∨ (z ∧ (Φ0 |z)).
Thus, for any satisfying assignment for Φ, either• x is true and Φ0 |x is satisfiable, or• y is true and Φ0 | y is satisfiable, or• z is true and Φ0 |z is satisfiable.
Each of the smaller formulas Φ0 |x, Φ0 | y, and Φ0 |z has at most n − 1 variables. If werecursively check all three possibilities, we get the running time recurrence
T (n) ≤ 3T (n − 1) + poly(n),whose solution is O(3n poly(n)). So we’ve actually done worse!
But these three recursive cases are not mutually exclusive! If Φ0 |x is not satisfiable,
then x must be false in any satisfying assignment for Φ. So instead of recursively checking
Φ0 | y in the second step, we can check the even simpler formula Φ0 |x̄ y = (Φ0 |x̄)| y.
Similarly, if Φ0 |x̄ y is not satisfiable, then we know that y must be false in any satisfying
assignment, so we can recursively check Φ0 |x̄ ȳz in the third step.
3Sat(Φ):if Φ = ∅return True(x ∨ y ∨ z) ∧ Φ0 ← Φ
if 3Sat(Φ0 |x)
return True
if 3Sat(Φ0 |x̄ y)return True
return 3Sat(Φ0 |x̄ ȳz)

The running time off this algorithm obeys the recurrence
T (n) = T (n − 1) + T (n − 2) + T (n − 3) + poly(n),where poly(n) denotes the polynomial time required to simplify boolean formulas, handle
control flow, move stuff into and out of the recursion stack, and so on.
How do we solve this recurrence? It isn’t simple enough to let us guess an accurate
solution and check it by induction. Fortunately, there is a standard mechanical solution
for all backtracking recurrences of the form
T (n) ≤ poly(n) +kXT (n − ai ),i=1

3

B. FASTER EXPONENTIAL ALGORITHMS

where k, a1 , a2 , . . . , ak are constants. Assume without loss of generality that the constants
ai are indexed in non-increasing order: a1 ≤ a2 ≤ · · · ≤ ak . The fundamental theoremof algebra implies that the characteristic polynomial
r

ak

−

k
X

r ak −aii=1(where r is a formal variable) has exactly k complex roots, some of which may beequal. Let λ be the root with largest magnitude. Then the solution to the recurrence
is T (n) = O(λn poly(n)). This technique is described in more detail in the appendix;
in particular, we can actually derived exact closed form solutions to backtracking-style
recurrences from the complete sequence of characteristic roots and base cases, if thepolynomial terms and base cases are specified exactly.
The recurrence T (n) = T (n − 1) + T (n − 2) + T (n − 3) + poly(n) has characteristic
polynomial r 3 − r 2 − r − 1, whose roots are approximately
1.83928676,−0.419643337 + 0.60629073i,−0.419643337 − 0.60629073i.

(Thank you, Wolfram Alpha!) The first root has larger magnitude than the other two, so
we get the solution
T (n) = O(λn poly(n)) = O(1.83929n ).
(Notice that we cleverly eliminated the polynomial noise by ever so slightly increasing
the base of the exponent.)

Pure Literals
We can improve this algorithm further by eliminating pure literals from the formula
before recursing. A literal x is pure in if it appears in the formula Φ but its negation x̄
does not. It’s not hard to prove (hint, hint) that if Φ has a satisfying assignment, then it
has a satisfying assignment where every pure literal is true. If Φ = (x ∨ y ∨ z) ∧ Φ0 has
no pure literals, then some clause in Φ contains the literal x̄, so we can writeΦ = (x ∨ y ∨ z) ∧ (x̄ ∨ u ∨ v) ∧ Φ0for some literals u and v (each of which might be y, ȳ, z, or z̄). It follows that thefirst recursive formula Φ|x contains the clause (u ∨ v). We can recursively eliminate thevariables u and v just as we eliminated the variables y and x in the second and thirdcases of our previous algorithm:
Φ|x = (u ∨ v) ∧ Φ0 |x = (u ∧ Φ0 |xu) ∨ (v ∧ Φ0 |x ūv).
Our new faster algorithm is shown in Figure ??. The running time T (n) of thisalgorithm satisfies the recurrence
T (n − 1)
T (n) = poly(n) + max
2T (n − 2) + 2T (n − 3)4

B.1. 3SAT

Faster3Sat(Φ):
if Φ = ∅return True
if Φ has a pure literal x
return Faster3Sat(Φ|x)(x ∨ y ∨ z) ∧ (x̄ ∨ u ∨ v) ∧ Φ0 ← Φ
if Faster3Sat(Φ|xu)
return True
if Faster3Sat(Φ|x ūv)
return True
if Faster3Sat(Φ|x̄ y)return True
return Faster3Sat(Φ|x̄ ȳz)
Figure B.1. A faster backtracking algorithm for 3SAT.

To solve this recurrence, we solve each case separately and take the larger of the twosolutions. Here, the comparison is easy; the first case yields a polynomial bound, while
the second case clearly yields an exponential bound, so for purposes of worst-caseanalysis, we can simplify the recurrence to T (n) = O(poly(n)) + 2T (n − 2) + 2T (n − 3).
The solution to this simpler recurrence is
T (n) = O(λn poly(n)) = O(1.76930n ),where λ ≈ 1.76929235 is the largest root of the characteristic polynomial r 3 − 2r − 2.

Local Search
We can get an even faster algorithm using a different backtracking strategy, called local
search. Instead of constructing a satisfying assignment recursively, we search for a paththrough the set of all assignments that ends at a satisfying assignment.
The Hamming distance between two different assignments is the number of variables
where the two assignments differ.2 Suppose we could somehow magically find an
assignment that is almost satisfying, meaning that its Hamming distance from somesatisfying assignment is small. Then instead of searching over the entire space of 2n
assignments, we only need to look at the assignments that are close to the assignment
we already have. Moreover, we can guide the search by considering only the clauses thatare not satisfied by our current assignment.
To make this concrete, let A be our current assignment, and suppose there is asatisfying assignment A∗ that has Hamming distance r from A. Consider any clause of Φ
2Richard Hamming was an early giant of computer and information science, who earned PhD in
mathematics at Illinois in 1942, programmed IBM calculating machines for the Manhattan project in 1945,
and then went on to create the first error-correcting codes. Arguably the greatest recognition of hisachievements is that his name is attached to the number of indices where two bit vectors differ.

5B. FASTER EXPONENTIAL ALGORITHMS

that is not satisfied by A; at least one the three variables in that clause has a different
value in A∗ . Thus, if we change that particular variable’s value, the resulting assignment
has Hamming distance r − 1 from A∗ . Of course, we don’t know which variable to change,
so we have to try all three of them. And we don’t know the target assignment A∗ , so wejust check at every stage of recursion whether our current assignment is satisfying. The
resulting backtracking algorithm, shown in Figure ??, runs in O(3 r poly(n)) time.
Local3Sat(Φ, A, r):
if A satisfies Φreturn True
if r = 0
return False
C ← any clause of Φ that A does not satisfy
x, y, z ← variables of C
A[x] ← ¬A[x]if Local3Sat(Φ, A, r − 1) = True
return True
A[x] ← ¬A[x]A[ y] ← ¬A[ y]if Local3Sat(Φ, A y , r − 1) = True
return True
A[ y] ← ¬A[ y]A[z] ← ¬A[z]return Local3Sat(Φ, Az , r − 1)
Figure B.2. A local search algorithm for 3SAT.

It must be emphasized that the local search algorithm is not explicitly considering
every assignment within Hamming distance r of the starting assignment A.
Now we apply the following trivial observation: In any satisfying truth assignment,
either at least half the variables are True or at least half the variables are False. Thus,
every satisfying assignment has Hamming distance at most n/2 from either the all-Trueassignment or the all-False assignment. So using the local search strategy, we can solve
3Sat in O(3n/2 poly(n)) = O(1.73206n ) time.
ªRandom Starting Assignments

We can improve the local search algorithm further, at the expense of a small probabilityof a false negative, by repeatedly choosing random starting assignments and searching
within a small radius of each.
First let’s do some preliminary math. Let V(r ) denote the number of assignments
within Hamming distance r of any fixed assignment. Suppose we run the local searchalgorithm starting with a random assignment; let P(r) denote the probability thatthe algorithm finds a satisfying assignment (assuming one exists). A simple counting
6B.1. 3SATargument implies that P(r ) ≥ V(r )/2n . If we choose N (r) random assignments and run
the local search algorithm starting at each one, the probability of not finding a satisfying
assignment (if one exists) is at most (1 − P(r))N (r) . Thus, if we set N(r ) = n2n /V(r ),this failure probability is at most
(1 − P(r))

n2n /V (r)

n

 n
V (r) 2 /V (r)≤1− n≤ e−n .
2

The overall running time of our algorithm is

 n r

n
2 3
r
O(N (r) 3 poly(n)) = O· 3 poly(n) = O
poly(n) .
P(r)
V (r)


r

To complete the analysis, we need to estimate the volume V (r) and choose anappropriate
value of r. For any constant 0 < α < 1, Stirling’s approximation n! ∼p
2πn (n/e)n implies the lower boundV (αn) =

r  
X
n
i=0

i

p 
= Ω H(α)n / nwhere H(α) is the binary entropy function:
H(α) = α 
1−α
1
1
.
α
1−α

Thus, if we set r = αn, the running time of our algorithm becomes
2n 3αnα1−α nOpoly(n)
=
O
2(3α)
(1
−
α)
poly(n)H(α)n

We can find the value of α that minimizes the base of the exponential part of this upperbound using a bit of calculus.
ddln (3α)α (1 − α)1−α =α ln(3α) + (1 − α) ln(1 − α)dαdα
= ln(3α) − ln(1 − α) = 0=⇒ α = 1/4.
Finally, if we set α = 1/4 (or equivalently, r = n/4), the algorithm runs innO 2(3/4)1/4 (3/4)3/4 poly(n) = O (3/2)n poly(n) time.
7

B. FASTER EXPONENTIAL ALGORITHMS

Further Extensions
Naturally, these approaches can be extended much further. Since 1998, at least fifteen
different 3Sat algorithms have been published, each improving the running time bya small amount; while a few of these improvements use pure backtracking, most ofthem are based on some variant of local search. For example, in 1999, Uwe Schöning
the running time of the randomized local search algorithm to O((4/3)n poly(n)), stillwith an exponentially small error probability, by replacing the backtracking search witha random walk of length 3n. As of 2016, the fastest deterministic algorithm for 3Sat
runs in O(1.3303n ) time3 , and the fastest randomized algorithm runs in O(1.30704n )expected time4 , but there is good reason to believe that these are not the best possible.
There is a thriving industry of practical Sat solvers, which combine backtracking,local search, random restarts, and other more sophisticated algorithmic techniques withdomain-specific heuristics. With these tools in hand, most real-world instances of Sat
are actually easy to solve in practice; modern Sat solvers routinely resolve instanceswith millions of variables and clauses. Sat solvers have become an indispensable tool inseveral areas of computing, including hardware and software verification, operations
research, and computational biology. The practically of Sat does not contradict thefact that the fastest algorithms require exponential time in the worst case; it just meansthat the worst case is rare in practice. Unfortunately, a proper discussion of practicaltechniques for Sat is beyond both the scope of this text and the expertise of its author.

B.2

Maximum Independent Set

Now suppose we are given an undirected graph G and are asked to find the size of thelargest independent set, that is, the largest subset of the vertices of G with no edges
between them. Once again, we have an obvious recursive algorithm: Try every subset ofnodes, and return the largest subset with no edges. Expressed recursively, we obtain thefollowing algorithm, where N (v) denotes the neighborhood of v: the set containing v
and all of its neighbors.
MaximumIndSetSize(G):if G = ∅return 0elsev ← any node in G
withv ← 1 + MaximumIndSetSize(G \ N (v))
withoutv ← MaximumIndSetSize(G \ {v})return max{withv, withoutv}.
3

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto. Derandomizing the HSSW algorithm for 3-SAT.
Algorithmica 67(2):112–124 (2013)
4
Timon Hertli. 3-SAT faster and simpler: Unique-SAT Bounds for PPSZ gold in general. SIAM J. Comput.
43(2):718–729 (2014).

8B.2. Maximum Independent Set

Our algorithm exploits the fact that if an independent set contains v, then bydefinition it contains none of v’s neighbors. In the worst case, v has no neighbors, so
G \ {v} = G \ N (v). Thus, the running time of this algorithm satisfies the recurrence
T (n) = 2T (n − 1) + poly(n) = O(2n poly(n)). Surprise, surprise.
This algorithm is mirroring a crude recursive upper bound for the number of maximal
independent sets in a graph; an independent set is maximal if every vertex in G iseither already in the set or a neighbor of a vertex in the set. If the graph is non-empty,
then every maximal independent set either includes or excludes each vertex. Thus, thenumber of maximal independent sets satisfies the recurrence M (n) ≤ 2M (n − 1), withbase case M (1) = 1. We can easily guess and confirm the solution M (n) ≤ 2n − 1. The
only subset that we aren’t counting with this upper bound is the empty set!

Smarter Case Analysis
We can speed up our algorithm by making several careful modifications to avoid theworst case of the running-time recurrence.
Degree 0. If any vertex v has no neighbors, then N (v) = {v}, and both recursive calls
consider a graph with n − 1 nodes. But in this case, v is in every maximal independent
set, so one of the recursive calls is redundant. On the other hand, if v has at least
one neighbor, then G \ N (v) has at most n − 2 nodes. So now we have the following
recurrence.
T (n) ≤ poly(n) + maxT (n − 1)T (n − 1) + T (n − 2)n= O(1.61804 )As before, the upper bound is derived by solving each case separately using characteristic
polynomials and taking the larger of the two solutions. The first case gives us T (n) =poly(n); the second case yields our old friends the Fibonacci numbers. Here and in later
multi-case recurrences, I’ve typeset the worst case of the recurrence in bold.
Degree 1. We can improve this bound even more by examining the new worst case:some vertex v has exactly one neighbor w. In this case, either v or w appears in every
maximal independent set. However, given any independent set that includes w, removing
w and adding v creates another independent set of the same size. It follows that somemaximum independent set includes v, so we don’t need to search the graph G \ {v}, and
the G \ N (v) has at most n − 2 nodes. On the other hand, if the degree of v is at least 2,
then G \ N (v) has at most n − 3 nodes.
9B. FASTER EXPONENTIAL ALGORITHMS

T (n) ≤ poly(n) + max

T (n − 1)T (n − 1) + T (n − 3)

T (n − 2)= O(1.46558n )The base of the exponent is the largest root of the characteristic polynomial r 3 − r 2 − 1.
Degree ≥ 3. Now the worst-case is a graph where every node has degree at least 2;
we split this worst case into two subcases. If G has a node v with degree 3 or more, thenG \ N (v) has at most n − 4 nodes. Otherwise (since we have already considered nodes ofdegree 0 and 1), every node in G has degree 2. Let u, v, w be a path of three nodes in G
(possibly with u adjacent to w). In any maximal independent set, either v is present andu, w are absent, or u is present and its two neighbors are absent, or w is present and its
two neighbors are absent. In all three cases, we recursively count maximal independent
sets in a graph with n − 3 nodes.

T (n − 1)








T (n − 2)
T (n) ≤ poly(n) + maxT (n − 1) + T (n − 4)






3T (n − 3)
= O(3n/3 poly(n))= O(1.44225n )p
3
The base of the exponent is 3, the largest root of the characteristic polynomial r 3 − 3.
The third case would give us a bound of O(1.38028n ), where the base is the largest rootof the characteristic polynomial r 4 − r 3 − 1.
Degree 2. Now the worst case for our algorithm is a graph with an extraordinarily
special structure: Every node has degree 2. In other words, every component of G is acycle. It is easy to prove that the largest independent set in a cycle of length k has sizebk/2c. So we can handle this case directly in polynomial time, with no recursion at all!

T (n) ≤ poly(n) + max

T (n − 1)T (n − 1) + T (n − 4)

T (n − 2)= O(1.38028n )Again, the base of the exponential running time is the largest root of the characteristic
polynomial r 4 − r 3 − 1. The final algorithm after all these improvements is shown in
Figure ??.
10

B.3. Dynamic Programming

MaximumIndSetSize(G):if G = ∅return 0
else if G has a node v with degree 0 or 1
return 1 + MaximumIndSetSize(G \ N (v))
else if G has a node v with degree greater than 2
withv ← 1 + MaximumIndSetSize(G \ N (v))
withoutv ← MaximumIndSetSize(G \ {v})return max{withv, withoutv}〈〈≤ n − 1〉〉〈〈≤ n − 4〉〉〈〈≤ n − 1〉〉else 〈〈every node in G has degree 2〉〉
total ← 0for each component of Gk ← number of vertices in the component
total ← total + bk/2c
return total
Figure B.3. A fast backtracking algorithm for MAXINDEPENDENTSET

Further Improvements
As with 3Sat, there are faster but increasingly complex algorithms for MaxIndependentSet. For example, in 1977, Bob Tarjan and Anthony Trojanowski published a complex
backtracking algorithm that considers several dozen cases, each with its own running
time recurrence. Most of these cases are clearly dominated by others; for example, even
without solving the recurrences, it’s easy to see that the recurrence T (n) ≤ poly(n) +T (n − 4) + T (n − 5) has a smaller solution than T (n) ≤ poly(n) + T (n − 3) + T (n − 5).
After discarding all such dominated cases, Tarjan and Trojanowski are left with therather impressive recurrence shown in Figure ??. The solution to this recurrence is
T (n) = O(1.256032 ) = O(2n/3 ), where the base of the exponent is the largest root of
the characteristic polynomial r 10 − r 8 − r 2 − 2 of the third case (in bold).
As of 2016, the fastest published algorithm for computing maximum independent setsruns in O(1.2114n ) time5 . However, in an unpublished technical report, Mike Robson
describes a computer-generated algorithm that runs in O(2n/4 poly(n)) = O(1.1889n )time; just the description of this algorithm requires more than 15 pages.6

B.3

Dynamic Programming
Warmup: Bellman-Held-Karp TSP in O(2n poly(n)) time. (Leave as exercise?)5

Nicolas Bourgeois, Bruno Escoffier, Vangelis Paschos, and Johan M. M. can Rooij. Fast algorithms formax independent set. Algorithmica 62(1):382–415, 2010.
6
John Michael Robson. Finding a maximum independent set in time O(2n/4 ). Technical report 1251-01,
LaBRI, 2001. 〈http://www.labri.fr/perso/robson/mis/techrep.ps〉.

ÆÆÆ
ÆÆÆ

11

B. FASTER EXPONENTIAL ALGORITHMS

T (n) ≤ poly(n) + max

T (n − 2) + T (n − 6)















































T (n − 2) + 2T (n − 8)
T (n − 2) + T (n − 8) + 2T (n − 10)
T (n − 3) + T (n − 5)
T (n − 4) + T (n − 6) + T (n − 8)
T (n − 4) + 2T (n − 7)

























T (n − 4) + T (n − 8) + 3T (n − 11)






T (n − 4) + 2T (n − 8) + T (n − 10)





T (n − 4) + T (n − 9) + 2T (n − 12)T (n − 4) + 4T (n − 10)





T (n − 5) + 4T (n − 9)T (n − 5) + 6T (n − 11) + 4T (n − 14) + T (n − 17)

Figure B.4. The (simpliﬁed!) running time recurrence for Tarjan and Trojanowski’s independent set algorithm.

3-coloring in O(2n poly(n)) time. Let OP T (X ) = TRUE if there is a 3-coloring in which every
vertex in X is red. ThenOP T (X ) =


FALSE



if X is not an independent set

TRUE
if G[V \ X ] is bipartiteW
OP T (X ∪ {v}) otherwisev∈V \X

Lawlar improved the running time to O(3n/3 poly(n)) by observing that we only need to careabout OP T (X ) when X is a maximal independent set. There are O(3n/3 ) maximal independent sets, which can be listed in O(3n/3 poly(n)) time.
Alternatively, 3-coloring in O(2n poly(n)) time by backtracking through the vertices insome ﬁxed whatever-ﬁrst order. Each vertex must be colored differently from is parent (andpossibly other vertices) and without loss of generality, the ﬁrst tow nodes are red and green,
respectively. So we consider only 2n−2 possible colorings, but memoization doesn’t help.
(Can we do better by looking in max-adjacency order?)ÆÆÆ

Lawler’s algorithm for chromatic number in O((1 + 31/3 )n poly n) time: Let OP T (X ) denotethe chromatic number of the subgraph G[X ] induced by the vertex subset X ⊆ V . Then¨
OP T (X ) =0
1 + min OP T (X \ I) maximal ind. set I in G[X ]if X = ∅otherwise

There are O(3k/3 ) maximal independent sets of size k, which can be listed in O(3k/3 poly(n))
time.

ÆÆÆ
12

B.3. Dynamic Programming

Other techniques to include?
• Horowitz-Sahni partitioning to solve SUBSETSUM in O(2n/2 poly(n)) time? (See also:
3SUM)• Decision via counting via Inclusion-Exclusion?

Exercises
1. (a) Prove that any n-vertex graph has at most 3n/3 maximal independent sets.
[Hint: Modify the MaximumIndSetSize algorithm so that it lists all maximal
independent sets.](b) Describe an n-vertex graph with exactly 3n/3 maximal independent sets, for every
integer n that is a multiple of 3.
2. (a) Describe an algorithm for kSat whose running time satisfies the recurrence
T (n) = 2T (n − 1) − T (n − k + 1) + poly(n).
(b) Describe an algorithm for kSat whose running time satisfies the recurrence
T (n) = T (n − 1) + 2T (n − 2) − 2T (n − k + 1) + poly(n).
[Hint: Modify the backtracking algorithms for 3Sat described in the text. No,
your algorithm will not make negative recursive calls.]ªDescribe an algorithm that solves 3Sat in O(φ n poly(n)) time, where φ = (1 +3. p
5)/2 ≈ 1.618034. [Hint: Prove that in each recursive call, either you have justeliminated a pure literal, or the formula has a clause with at most two literals. What
recurrence leads to this running time?]

4. Describe an algorithm to determine whether a graph is 4-colorable in O(2n poly(n))
time. [Hint: Consider red and green together, but separately from blue and yellow.]
5. (a) Prove the following upper bound for all constant 0 < α < 1: α  
1−α nαn  
X
n
n
1
1
≤
<
αn
i
α
1−α
i=0
[Hint: Expand the expression (α + (1 − α))n = 1 using the binomial theorem.](b) Prove the following lower bound for all constant 0 < α < 1:
   α 1−α npn
1
1≥· Ω(1/ n)
αn
α
1−α
p
p
[Hint: Use Stirling’s approximation: 2πn (n/e)n ≤ n! ≤ 2 πn (n/e)n .]Need a few more exercises.

ÆÆÆ
13

B. FASTER EXPONENTIAL ALGORITHMS© 2018 Jeff Erickson

14

http://algorithms.wtf