.Petr Hliněný, FI MU Brno, 2015 1 / 25 FI: MA010: Difficulty of Graph Problems
8 On Difficulty of Graph Problems
The primary point of this lecture is to address two related questions:
• How can one compare between easy and hard graph problems?
• How can one assess the difficulty of a newly formulated problem?
✷
Brief outline of this lecture
• Examples of easily (and efficiently) solvable graph problems.
• Colouring and Hamiltonicity – two traditional hard grah problems.
• How to assess difficulty of a problem – using problem reductions.
.Petr Hliněný, FI MU Brno, 2015 2 / 25 FI: MA010: Difficulty of Graph Problems
8.1 Some Easily Solvable Problems
During the course, we have seen several really simple algorithmic solutions for basic
questions on graphs, e.g. for:
• testing connectivity and finding the connected components, ✷
• computing the distance and a shortest path in a graph, ✷
• computing a minimum spanning tree in a weighted graph, ✷
• finding a maximum flow and a minimum cut in a network, ✷
• finding a maximum matching in a bipartite graph, ✷
• testing 2-colourability of graphs, ✷
• testing isomorphism of trees. ✷
Well, that was about the algorithm design, and what about the theory side?
.Petr Hliněný, FI MU Brno, 2015 3 / 25 FI: MA010: Difficulty of Graph Problems
Nice characterizations of problems
Such “easily solvable” problems typically come hand in hand with nice theoretical characterizations
of the solutions, and of their existence in greater generality. ✷
For example. . .
• Good characterizations of problems; either
– we have got an obvious or easily verifiable solution, or
– we can find an obvious or easily verifiable obstacle. ✷
Recall some examples of good characterizations:
• For connectivity in a graph; either
– we can find an x-y walk (or path) in the graph, or
– a vertex subset X ⊆ V such that x ∈ X, y ∈ X and no edge leaves X. ✷
• For maximum matching in a bipartite graph; either
– we can find a matching with k edges, or
– we have got a vertex cover with < k vertices. ✷
• For 2-colourability of a graph; either
– we can find a proper 2-colouring (bipartition), or
– a cycle of an odd length.
.Petr Hliněný, FI MU Brno, 2015 4 / 25 FI: MA010: Difficulty of Graph Problems
On the dark side
For problems which are “hard to solve”, nice theoretical characterizations of their solutions
typically do not (and cannot) exist, e.g.; ✷
• for the 3-colourability problem one can easily verify that a given colouring is
proper (or not), but that is not sufficient! ✷
• there is no known good way of showing that a 3-colouring does not exist in a
given graph, other than trying all possibilities.
Even though we have no such directly provable relation, an absence of a nice characterization
of the solutions usually indicates hardness of a problem. . . ✷
Much worse, for some other hard graph problems the correct solution is even not easily
verifiable; ✷
• considering, say, 4-choosability of a given graph, how can one verify that for all
possible assignments of lists of 4 colours a proper colouring does exist?
.Petr Hliněný, FI MU Brno, 2015 5 / 25 FI: MA010: Difficulty of Graph Problems
And Some More Involved Problems
Obviously, life is not always as easy as in the previous slides. . . ✷
There exist graph problems for which an efficient algorithmic solution exists, but both
the algorithms and related theoretical characterizations of their solutions are rather
involved, e.g.; ✷
• a maximum matching in general graphs, and a maximum weighted matching, ✷
• testing planarity and finding a plane drawing in linear time
(interestingly, the best algorithms are not dir. related to the Kuratowski thm.),
• the isomorphism of planar graphs in linear time (needs planarity as a tool). ✷
Though not so often, there are examples of problems having theoretically fast algorithms,
but which are practically unusable, e.g.; ✷
• the isomorphism of 3-regular graphs, ✷
• testing graph embeddability in (fixed) higher surfaces,
• possibility to draw a graph in the plane with, say, < 100 edge crossings, ✷
• the graph minor testing, and consequently all minor-closed decision properties.
.Petr Hliněný, FI MU Brno, 2015 6 / 25 FI: MA010: Difficulty of Graph Problems
A strange case of the isomorphism problem
• As we know from the graph exercises, there are many partial obstacles for isomorphism;
like different degree sequences, unequal numbers of triangles etc., and
many more. . . ✷Unfortunately, there is no known universal list of such obstacles.✷
• There is an easy practical heuristic algorithm for deciding and finding an isomorphism
between graphs:
– for each vertex v, compute a “hash code” composed of the numbers of
vertices and edges at distance 1, 2, 3, . . . from v; ✷
– this can be recursively iterated, usually giving a complete distinction.
Where is the problem? ✷For “highly regular graphs”, the local neighbourhoods
of all vertices look the same, and we gain nothing from the heuristic. ✷
• To prove isomorphism, one can show the bijection. But how can one prove that
two graphs are not isomorphic while out of luck with finding some obstacle?✷
– Surprisingly, there is a cute universal (and randomized) solution:
Randomly choose one of the two graphs, permutate it and give the result
to the prover for a check. Repeat this. . . ✷
– If the prover is always able to tell which of the two graphs was chosen, then
everybody may be pretty sure that the two graphs are indeed not isomorphic.
.Petr Hliněný, FI MU Brno, 2015 7 / 25 FI: MA010: Difficulty of Graph Problems
8.2 Colouring and Hamiltonicity
This is one of the first difficult graph problems that always comes in mind:
The k-Colouring Problem (recall Lecture 6)
For a given (loopless) graph G, decide whether χ(G) ≤ k.
✷
• Easily solvable for k = 1, 2. . .
• Already for k = 3 this problem becomes hopelessly hard; ✷even in planar graphs
of maximum degree 4. ✷
• Even if it is promissed that a graph G is 3-colourable, we do not know of any
efficient algorithm that would properly colour G by, say, 1000000 colours!
Hamiltonian cycle / path = Hamiltonovská kružnice / cesta
.Petr Hliněný, FI MU Brno, 2015 8 / 25 FI: MA010: Difficulty of Graph Problems
Hamiltonian Graphs
Another typical hard graph question is that about an existence of a cycle or a path through
all the vertices of the given graph (an older and simplified setting of a “travelling salesman”):
s s
ss
s s
ss
s s
s
s
s
s s
s
s
s
✷
Definition: A cycle C in a graph G is a Hamiltonian cycle if C spans all vertices of G.
Analogously, a Hamiltonian path P in G is a path in G spanning all the vertices. ✷
A graph G is Hamiltonian if G contains a Hamiltonian cycle.
The same terminology applies in the case of digraphs with dir. cycles and paths. ✷
The Hamiltonian cycle problem is also related to some attempts to solve the 4 colour problem:
Precisely, if every 3-regular planar graph was Hamiltonian, then the 4 colour theorem would
follow easily. ✷Unfortunately, this Hamiltonicity claim later turned out not to be true. . .
tournament = turnaj (spec. druh or. grafu)
.Petr Hliněný, FI MU Brno, 2015 9 / 25 FI: MA010: Difficulty of Graph Problems
Hamiltonian tournaments
Some special properties related to Hamiltonian paths and cycles hold in a special case.
Definition: A digraph G is called a tournament if, for every vertex pair u, v ∈ V (G),
u = v, exactly one of the arcs (u, v), (v, u) is in G.
In other words, a tournament on n vertices results by arbitrarily orienting each edge of Kn. ✷
Proposition 8.1. Every tournament G contains a Hamiltonian (directed) path.
Proof: We apply a straightforward induction on n, the number of vertices of G. ✷
• If n ∈ {1, 2}, then G itself is a directed path.
• Assume n ≥ 3, and choose v0 ∈ V (G) arbitrarily. Form G0 = G \ v0 by deleting
the vertex v0, and let P = (v1, v2, . . . , vn−1) be a dir. Hamiltonian path in G0
(in this order of vertices), which exists by the induction assumption. ✷
• If (vn−1, v0) ∈ E(G), then P with v0 at the end is a Ham. path in G. Similarly,
if (v0, v1) ∈ E(G), then P prefixed with v0 is a Ham. path in G. ✷
Otherwise, let j ∈ {1, . . . , n − 1} be the least index such that (v0, vj) ∈ E(G),
and hence (vj−1, v0) ∈ E(G). Then (v1, . . . , vj−1, v0, vj, . . . , vn−1) is a dir.
Hamiltonian path in G.
✷
.Petr Hliněný, FI MU Brno, 2015 10 / 25 FI: MA010: Difficulty of Graph Problems
Proposition 8.2. A tournament G contains a Hamiltonian (directed) cycle if, and only
if, G is strongly connected.
Proof: In the forward direction, a (Hamiltonian) directed cycle is strongly connected
and it spans all the vertices of G, and so G is strongly connected. ✷
Conversely, assume that D ⊆ G is a longest directed cycle in G, and x ∈ V (G)\V (D).
Let the vertices of D be named v1, v2, . . . , vk in this cyclic order. What direction are
the arcs between D and x?
s s s
sss
D
v1
vk
s x
✷
• If the directions are mixed (to and from x), then there is an index i such that
both vix, xvi+1 ∈ E(G), and hence (D \ vivi+1) ∪ {vix, xvi+1} is a cycle longer
than D, a contradiction. ✷
• If the direction is the same, say, all arcs go from D to x, then we finish as follows:✷
By strong connectivity of G, there is a directed path P from x to D, say ending
in vj ∈ V (D). Hence again, (D\vj−1vj)∪{vj−1x}∪P is a cycle longer than D,
a contradiction.
✷
.Petr Hliněný, FI MU Brno, 2015 11 / 25 FI: MA010: Difficulty of Graph Problems
Dirac’s theorem
Theorem 8.3. Every graph G on n ≥ 3 vertices and with minimum degree ≥ n/2 is
Hamiltonian. ✷
Proof (a sketch): Let P ⊆ G be a longest possible path in the graph G, such that the
vertices on P occur in this order; (u0, u1, . . . , uk). ✷It is easy to claim:
• every neighbour of u0 or uk belongs to P (since otherwise we prolong P),
• since dG(u0), dG(uk) ≥ 1
2 n ≥ 1
2 (k + 1), by the pigeon-hole principle, there is
0 < i < k such that u0ui+1 ∈ E(G) and ukui ∈ E(G) (draw a picture), ✷
• consequently, we have got a cycle C ⊆ G on V (P) in the cyclic order of vertices
(u0, ui+1, ui+2, . . . , uk, ui, ui−1, . . . , u0). ✷
That is all since, if there was a vertex x ∈ V (G) \ V (C) (missed by C), then x
would have a neighbour on C and we would get another path longer than original P,
a contradiction. Hence P spans all the vertices of G which is Hamiltonian. ✷
* Redukce mezi problémy *
.Petr Hliněný, FI MU Brno, 2015 12 / 25 FI: MA010: Difficulty of Graph Problems
8.3 Problem Reductions
The term polynomial reduction is formally defined in every computational complexity
course. However, this course is not on complexity but on graphs, and so we stay with
an informal explanation of the concept.
• Imagine that somebody asks us to solve an instance of Problem A, which we
do not know how to solve, but we have a nice algorithm / solution for another
Problem B. ✷
• If we are lucky, then we can take an input of Problem A, and transform it to an
input of Problem B such that a (possible) solution is preserved (meaning that we
can always “decode” a solution for A from a solution for such transformed B). ✷
• Obviously, our tranformation should be “easy and efficient”. We say that we have
got a
reduction from Problem A to Problem B.
If we have got a reduction from A to B then, informally, Problem A is not harder (of
at most the same difficulty) than Problem B (plus the difficulty of the reduction).
From a different point of view; if we know that Problem A cannot be solved nicely,
then neither can Problem B (a “hardness reduction”).
.Petr Hliněný, FI MU Brno, 2015 13 / 25 FI: MA010: Difficulty of Graph Problems
Example 8.4. Show that the following two problems are of the same difficulty:
A: to decide whether a given graph G has a Hamiltonian path,
B: to decide whether G has a Hamiltonian path starting in a given vertex. ✷
To provide a proof, we have to show two problem reductions; from A to B and from B
to A. We start with the latter one.
• (From B to A): Imagine somebody asks for a Hamiltonian path in G starting
with v ∈ V (G), and we could only solve the general Ham. path problem. ✷
Then we construct a graph G′
from G by adding a new vertex v′
adjacent only
to v. Any Ham. path in G′
has to start in v′
and continue with v, and so it gives
a Ham. path in G starting with v. ✷
• (From A to B): We could solve general Ham. path by asking for a Ham. path
starting in every vertex of G separately, but there is a much nicer alt. solution.
We construct a graph G′′
from given G by adding a new vertex x adjacent to all
V (G), and ask for a Ham. path starting in x. Trivially, a Ham. path in G exists
iff such a cycle can be prolonged till x to make a Ham. path in G′′
from x.
✷
.Petr Hliněný, FI MU Brno, 2015 14 / 25 FI: MA010: Difficulty of Graph Problems
Example 8.5. Show that the following two problems are of the same difficulty:
A: to decide whether a given graph G is 3-colourable,
B: to decide whether a given graph G is 4-colourable. ✷
We proceed as in the previous example, giving the two desired reductions. To reduce
from 3-colourability to 4-colourability is very easy, simply make a graph G′
from original
G by adding a new vertex x adjacent to all V (G). Then every 3-colouring of G is in
a one-to-one correspondece with a 4-colouring of G′
using colour 4 at the vertex x. ✷
A converse reduction is more involved and tricky. Recall; we would like to test whether
G is 4-colourable using an “oracle” which answers about 3-colourability of a graph.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
✷
.Petr Hliněný, FI MU Brno, 2015 15 / 25 FI: MA010: Difficulty of Graph Problems
Example 8.5. Show that the following two problems are of the same difficulty:
A: to decide whether a given graph G is 3-colourable,
B: to decide whether a given graph G is 4-colourable. ✷
A reduction from B to A is more involved and tricky. Recall; we would like to test
whether G is 4-colourable using an “oracle” which answers about 3-colourability of a
graph G′′
. We sketch a construction of G′′
from original G as follows:
• one new vert. y in G′′
, to be coloured by 3 (up to symm.) in every 3-col. of G′′
;✷
• for every v ∈ V (G), two new vert. v1
, v2
adjacent to y, to be col. from {1, 2};✷
• and for every edge uv ∈ E(G), a copy of the following gadget:
s
s
s
s
❢
❢
❢
❢
s
s
s
s
u1
u2
v1
v2
sy
✷
Observe that this gadget of G′′
is 3-colourable iff the colour pair of (u1
, u2
) is distinct
from that of (v1
, v2
). Hence, it “simulates” 4-colourability of G with colours formed
by the four pairs (1, 1), (1, 2), (2, 1), (2, 2) available for (u1
, u2
) and (v1
, v2
). ✷
decision problem = rozhodovací problém
.Petr Hliněný, FI MU Brno, 2015 16 / 25 FI: MA010: Difficulty of Graph Problems
Class N P and N P-completeness
Decision problems
• Decision problems are those, roughly saying, whose answer can be Yes/No. ✷
• This seems quite restrictive, however;
– for the colouring problems, we usually ask if a graph G is k-colourable,
meaning whether χ(G) ≤ k, but not about the precise value of χ(G), ✷
– simiarly, in the clique and independent set problems, we may ask whether
ω(G) ≤ k and α(G) ≤ k, and ✷
– knowing how to solve the decision variant of a problem usually means we
can also find a witnessing solution. ✷
Class N P
• A prominent rank among graph decision problems belongs to those problems in
which an answer Yes can be verified, with the help of a suitable advice (oracle),
by an efficient procedure/algorithm. ✷
– In computational complexity, the class of such problems is called NP. ✷
• Actually, the decision version of most common graph problems are of this kind.
For example, in the colouring problem the advice is a proper colouring of the given
graph which can be readily verified. Likewise for the Hamiltonian problem, the advice
is a Hamiltonian cycle, etc.
SAT = problém splnitelnosti logických formulí v konjunktivní normální formˇe
.Petr Hliněný, FI MU Brno, 2015 17 / 25 FI: MA010: Difficulty of Graph Problems
The Satisfiability problem
The following one is the “master NP-complete” problem:
Problem 8.6. 3-SAT (a special version of satisfiability SAT)
The following problem is NP-complete (reading “hardest in NP”), meaning that it
belongs to the class NP and no other problem in NP can be more difficult: ✷
Input: A propositonal logic formula Φ in a conjunctive normal form, such that every
clause of Φ contains ≤ 3 literals.
Output: Is there a valuation of the Φ-variables that makes Φ true?
For instance, Φ ≡ (x1 ∨ ¬x3 ∨ x4) ∧ (x2 ∨ ¬x4) ∧ (¬x1 ∨ x2 ∨ x3). ✷
The true informal meaning of NP-completeness of a problem is as follows;
• “I am the hardest problem in the very natural class NP, and if you could solve me,
then you would be able to solve everything in NP.” ✷
• Consequently, it is very likely that NP-complete problems cannot be solved nicely
(again, we refer to computational complexity courses for a precise definition of this).
• As it turns out, many typical problems in graph theory are of the same, “highest”,
difficulty—they are NP-complete. We will outline this fact, in a series of problem
reductions, next.
.Petr Hliněný, FI MU Brno, 2015 18 / 25 FI: MA010: Difficulty of Graph Problems
8.4 Sample Reductions for Hard Problems
Problem 8.7. 3-COL (3-Colouring of graphs)
The following problem is as hard as SAT:
Input: A graph G.
Output: Can the vertices of G be properly coloured using three colours?
Proof (a sketch): The problem is in NP and we construct a reduction from 3-SAT. ✷
For a given formula Φ we construct a graph GΦ: The basis of the construction of GΦ is
a triangle with vertices denoted by X, T, F. Each variable xi in Φ is assigned a vertex
pair adjacent to X. Each clause of Φ is assigned a subgraph on 6 vertices (three of
them adjacent to T ), as in the picture. Then the remaining free “halfedges” are joined
together in the way corresponding to the literals (xi or ¬xi) in the clauses.
s
s
s
X
F
T
s
s
s
s
to clauses ←
(val. T or F)
x1
¬x1
...
xi
¬xi
s
s
s
...
ss
s
e.g. (x1 ∨ ¬xi ∨ . . . ) :
→ to variables
(while all-F not colourable!)
Then one may easily check that GΦ has a 3-colouring iff Φ is satisfiable. ✷
.Petr Hliněný, FI MU Brno, 2015 19 / 25 FI: MA010: Difficulty of Graph Problems
Problem 8.8. IS (Independent Set)
The following problem is as hard as SAT and 3-COL:
Input: A graph G, and an integer k.
Output: Is there an independent set (i.e., a subset of the vertices with no edges between
them) of size at least k in G? ✷
Proof: The problem is in NP and we construct a reduction from 3-COL.
Let H be a graph on n vertices which should be 3-coloured. We set k = n, and
construct a graph GH made of three disjoint copies of H as shown in the picture:
s
s
s
s
s
H
v
❀
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
GH
Tv
❢
❢
❢
❢
❢
Assume c : V (H) → {1, 2, 3} is a 3-colouring of H. Then one can choose k = n indep.
vertices in GH; for each v ∈ V (H) choosing the c(v)-th copy of v in the graph GH . ✷
Convers., if I is an indep. set in GH of size k = n, then every triangle Tv, v ∈ V (H),
intersects I prec. in one vertex. This determines one of three colours for v in H. ✷
VC = vrcholové pokrytí
.Petr Hliněný, FI MU Brno, 2015 20 / 25 FI: MA010: Difficulty of Graph Problems
Definition: A vertex cover in a graph G is such a set C ⊆ V (G) that every edge of
G is incident with a vertex of C, i.e. G − C is independent.
Problem 8.9. VC (Vertex Cover)
The following problem is as hard as SAT and IS:
Input: A graph G, and an integer ℓ.
Output: Is there a vertex cover of size at most ℓ in G? ✷
s s
ss
s s
ss
❢
❢
❢
❀
s s
ss
s s
ss
❢
❢
❢ ❢
❢
independent set vertex cover
Proof: The problem is in NP and we construct a really trivial reduction from IS.
Notice that the complement C = V (G)\I of an arbitrary independent set I is actually
a vertex cover, and vice versa. So the reduction works with the same graph G and
with ℓ = n − k (where k is the desired IS size). ✷
DOM = dominující množina
.Petr Hliněný, FI MU Brno, 2015 21 / 25 FI: MA010: Difficulty of Graph Problems
Definition: A dominating set in a graph G is a set D ⊆ V (G) such that every vertex
of G not in D has a neighbour in D.
Problem 8.10. DOM (Dominating set)
The following problem is as hard as SAT and VC:
Input: A graph G, and an integer ℓ.
Output: Is there a dominating set of size at most ℓ in G?✷
Proof: The problem is in NP and we construct an easy reduction from VC.
Given any graph H, we construct an input graph GH for the DOM problem as follows:
For every edge e ∈ E(H), a new vertex ve is added, forming a triangle with e.
s s
ss
s
❢
❢❢
❀
s s
ss
s
s
s
s
s
s
s
❢
❢❢
vertex cover dominating set
Now a vertex cover of the former graph is the same as a dominating set in the latter
graph (any domin. set in the latter can be “pushed away” from the new vertices). ✷
.Petr Hliněný, FI MU Brno, 2015 22 / 25 FI: MA010: Difficulty of Graph Problems
Problem 8.11. HC (Hamiltonian cycle, directed)
The following problem is NP-complete:
Input: A digraph G.
Output: Is there a directed cycle in G passing through all the vertices?✷
Proof (a sketch): The problem is in NP and we outline a reduction from VC.
Given any graph H and integer ℓ (an instance of VC), we construct a digraph GH for the
HC problem as follows. Every vertex v ∈ V (H) is transformed into a directed cycle Cv
of length dH(v), and then each arc of Cv with both endvertices is further transformed
into one side of a gadget as in the following picture, for every edge uv ∈ E(H):
s
s
s
s
arc of Cu arc of Cv
s
s
s
s
s
edge uv ∈ E(H) gadget:
❢
The point of this gadget is that while traversing it, one has to return to the same Cu
as started from. ✷Finally, exactly ℓ new vertices are added to GH as adjacent to and
from every one of transformed Cv’s (this models that we can “jump across” altogether
ℓ of Cv’s while covering all the edge gadgets). ✷
.Petr Hliněný, FI MU Brno, 2015 23 / 25 FI: MA010: Difficulty of Graph Problems
Problem 8.12. HAM (Hamiltonian cycle)
The following problem is as hard as SAT and HC:
Input: A graph G.
Output: Is there an (undirected) cycle in G passing through all the vertices? ✷
Proof:
sv ❀ s s s
Pv
It is an easy reduction from the previous problem HC. Each vertex v of a directed graph
H is replaced with three vertices forming a path Pv in the graph GH. ✷
Then the directed edges coming into v are joined to the first vertex of Pv, while the
edges leaving from v are joined to the last vertex of Pv. Having to travers also the
middle vertex of Pv now “enforces” the right direction of passing throuh each Pv as
through the original vertex v of H. ✷
.Petr Hliněný, FI MU Brno, 2015 24 / 25 FI: MA010: Difficulty of Graph Problems
8.5 Appendix: The interesting story of Vertex Cover
Consider the (at first glance) very similar problems of a vertex cover and of a dominating
set in a graph—both are among the classical NP-complete problems. Yet, we discover
a huge difference between them, briefly outlined as follows. ✷
• If, in the computational complexity analysis, we focus on the value of the input
parameter k, then we still cannot solve Dominating Set in a better way than
exhaustively checking (almost) all k-tuples of vertices.
Even when k is fixed small, say k = 10, 20, this an intractable problem. ✷
What does it mean “cannot solve”?
In this particular case, a solution to Dominating Set significantly faster than checking
all k-tuples of vertices, would violate the Exponential Time Hypothesis. ✷
• On the other hand, a Vertex Cover of size k can be decided by a very simple
algorithm running in time O(2k
· n), which is quite usable for small fixed values
of k such as k = 10, 20, giving actually a linear time algorithm!
.Petr Hliněný, FI MU Brno, 2015 25 / 25 FI: MA010: Difficulty of Graph Problems
Algorithm 8.14. k-VC (Vertex Cover)
For any fixed parameter k we are solving the following problem.
Input: A graph G.
Output: Is there a vertex cover of size at most k in G? ✷
We initialize C = ∅ and F = E(G).
• If F = ∅, then C is returned as a vertex cover.
If, otherwise, |C| ≥ k, then the return value is “NO”. ✷
• We pick an arbitrary edge f = uv ∈ F, and for each of its ends x = u, v we do:
– C′
= C ∪{x}, and the edge set F′
results from F by removing all the edges
incident with x in G;
– the algorithm is called recursively for G, C′
and F′
. ✷
Finally, how many (self-)recursive calls occurs in Algorithm 8.14 altogether? Every call
generates two further recursive calls, but only up to a fixed depth k. Hence the total
running time is asymptotically only O(2k
· n). ✷
Remark: The factor 2k
can be improved by more careful choice of branching. (2006: 1.2738k
)