Fixed-Parameter Algorithms, IA166
Sebastian Ordyniak
Faculty of Informatics
Masaryk University Brno
Spring Semester 2013
Bounded Search Tree
Bounded Search Tree
Bounded Search Tree
Skew separators
Outline
1 Bounded Search Tree
Skew separators
Vertex Coloring – a none standard parameterization
An alternative way of choosing the parameter
Bounded Search Tree – Summary
Bounded Search Tree
Skew separators
Definitions – digraphs
A directed graph or digraph is a tuple G = (V, A) such that
A is a set of pairs (u, v) with u, v ∈ V;
Elements of V and A are called the vertices and arcs of G,
respectively;
For a digraph G, V(G) denotes its vertex set and A(G) its
arc set.
If (u, v) ∈ A(G), then v is an out-neighbor of u and u is an
in-neighbor of v;
The out-degree(in-degree) of a vertex u is the number of
out-neighbors (in-neighbors) of u.
Bounded Search Tree
Skew separators
Definitions – Paths, cuts, reachability
Let G be a digraph, S ⊆ V(G), and T ⊆ V(G) such that S and
T are disjoint.
An (S, T)-path is a sequence of distinct vertices v0, . . . , vl
such that v0 ∈ S, vl ∈ T, and (vi, vi+1) ∈ A(G) for all
0 ≤ i < l;
T is reachable from S if G contains an (S, T)-path;
A set C ⊆ V(G) \ (S ∪ T) is an (S, T)-cut if T is not
reachable from S in G \ C;
MinCutG(S, T) denotes the size of a minimum (S, T)-cut in
G where MinCutG(S, T) = ∞ if no such cut exists.
Theorem
MinCutG(S, T) can be computed in polynomial time for all
S, T ⊆ V(G) (e.g., using Flows).
Bounded Search Tree
Skew separators
MINIMUM SKEW SEPARATOR (k-MSS) Parameter: k
Input: Digraph G, vertex sequences S = (s1, . . . , sl) and
T = (t1, . . . , tl) where all si have in-degree 0 and all ti have
out-degree 0, and an integer k.
Question: Does G have a skew-separator (SS) C of size at
most k, i.e., is there a C ⊆ V(G) \ (S ∪ T) such that |C| ≤ k
and for all j ≤ i, tj is not reachable from si in G \ C?
Why is this problem interesting?
It will demonstrate another non-trivial technique of
bounding the search tree size.
The algorithm for this problem is part of the recent FPT
algorithm for directed feedback vertex set (Major
Breakthrough!).
Bounded Search Tree
Skew separators
Reduction rules and easy cases
Let I = (G, S, T, k) be a k-MSS instance where
S = (s1, . . . , sl) and T = (t1, . . . , tl).
Observation (Rule 1)
If there is an arc from sl to some tj then I has no SS.
Observation (Rule 2)
If T is not reachable from sl and l ≥ 2 then
(G \ {sl, tl}, S \ {sl}, T \ {tl}) has a k-MSS iff I has a k-MSS.
Observation (Rule 3)
If sl has an out-neighbor u that has out-neighbors in T then
G \ {u} has a (k − 1)-MSS iff I has a k-MSS.
Bounded Search Tree
Skew separators
Reduction rules and easy cases
Let I = (G, S, T, k) be a k-MSS instance where
S = (s1, . . . , sl) and T = (t1, . . . , tl).
Observation (Rule 4)
If MinCutG(S, T) > k then I has no k-MSS.
Observation (Rule 5)
If l = 1 then G has a k-MSS iff MinCutG(S, T) ≤ k.
Observation
Rules 1–5 can be applied in polynomial time and at most
|V(G)| times.
Bounded Search Tree
Skew separators
A less trivial rule
Definition
For an out-neighbor u of sl we denote by G/(sl, u) the graph
obtained from G by contracting (sl, u) into sl and subsequently
removing all arcs coming into sl.
Theorem (Rule 6)
If sl has an out-neighbor u such that
MinCutG(sl, T) = MinCutG({sl, u}, T) then G has a k-MSS iff
G/(sl, u) has a k-MSS.
Bounded Search Tree
Skew separators
A less trivial rule
The correctness of Rule 6 follows from the following proposition
and theorem.
Proposition
Let u be an out-neighbor of sl. Then G has k-MSS that does
not contain u iff G/(sl, u) has a k-MSS.
Theorem 1
If sl has an out-neighbor u such that
MinCutG(sl, T) = MinCutG({sl, u}, T) then G has a MSS that
does not contain u.
Bounded Search Tree
Skew separators
A less trivial rule
The correctness of Rule 6 follows from the following proposition
and theorem.
Proposition
Let u be an out-neighbor of sl. Then G has k-MSS that does
not contain u iff G/(sl, u) has a k-MSS.
Proof:
Let C be a MSS that does not contain u in G then C is also a
MSS in G/(sl, u). For the reverse direction suppose C is a MSS
for G/(sl, u). Then C is also a MSS for G that does not contain
u.
Bounded Search Tree
Skew separators
Proof of Theorem 1
Proof:
Let Y be a minimum ({sl, u}, T)-cut in G which is a minimum
(sl, T)-cut in G that does not contain u. Let X be a minimum
MSS for I. If u /∈ X we are done, so assume u ∈ X. We define:
Z= X ∩ Y;
YB: the vertices in Y \ X that cannot reach T in G \ X;
YF : the vertices in Y \ X that can reach T in G \ X;
XB: the vertices in X \ Y that cannot reach T in G \ Y;
XF : the vertices in X \ Y that can reach T in G \ Y;
Hence: X = XB ∪ Z ∪ XF and Y = YB ∪ Z ∪ YF .
Bounded Search Tree
Skew separators
Proof of Theorem 1, continued
We need the following claims:
Claim 1
Y = YB ∪ Z ∪ XB is an (sl, T)-cut in G.
Claim 2
X = XF ∪ Z ∪ YF is a MSS for I.
Bounded Search Tree
Skew separators
Proof of Theorem 1, continued
Assuming Claim 1 and 2 hold, we proof Theorem 1 as follows:
Proof (Theorem 1):
Y is a minimum (sl, T)-cut, hence |Y| ≤ |Y | and
|YB| + |Z| + |YF | ≤ |YB| + |Z| + |XB| and consequently
|YF | ≤ |XB|;
Therefore,
|X | = |XF | + |Z| + |YF | ≤ |XF | + |Z| + |XB| = |X|, hence X
is a minimum MSS;
u /∈ XF because otherwise T would be reachable from u in
G \ Y and hence from sl, but Y is an (sl, T)-cut.
u /∈ Z ∪ YF ⊆ Y be the choice of Y and so u /∈ X .
Bounded Search Tree
Skew separators
Proof of Claim 1
Proof of Claim 1 (Y = YB ∪ Z ∪ XB is an (sl, T)-cut in G):
Suppose not and let P be an (sl, T)-path in G \ Y . Let w be the
first vertex of P in XF ∪ YF . Because Y and X are (sl, T)-cuts,
Y \ Y = YF , and X \ Y = XF such a vertex must exists.
If w ∈ XF then P = Psl ,w is a path in G \ Y and by the definition
of XF there is a path P from w to T in G \ Y. Hence, P ◦ P is
an (sl, T)-path in G \ Y, a contradiction.
If w ∈ YF then P = Psl ,w is a path in G \ X and by the definition
of YF there is a path P from w to T in G \ X. Hence, P ◦ P is
an (sl, T)-path in G \ X, a contradiction.
Bounded Search Tree
Skew separators
Proof of Claim 2
Proof of Claim 2 (X = XF ∪ Z ∪ XF is a MSS for I):
Suppose not and let P be an (sl, T)-path in G \ X . Because X
is a MSS and X \ X = XB the path P contains a vertex in XB.
Let w be the last vertex of P in XB and P = Pw,tj
.
Because P is not a path in G \ Y (by the definition of XB and
Y \ X = YB, P contains a vertex x ∈ YB. Let P = Px,tj
(because x = w P is strictly shorter than P ).
Because P is not a path in G \ X (by the definition of YB) and
X \ X = XB, P contains a vertex y ∈ XB. This contradicts the
choice of w.
Bounded Search Tree
Skew separators
A branching rule!?
Theorem (Rule 6)
If sl has an out-neighbor u such that
MinCutG(sl, T) = MinCutG({sl, u}, T) then G has a k-MSS iff
G/(sl, u) has a k-MSS.
Branching Rule
If sl has an out-neighbor u, then G has a k-MSS iff either
G \ {u} has a (k − 1)-MSS or G/(sl, w) has a k-MSS.
Bounded Search Tree
Skew separators
A branching algorithm?!
Let I = (G, S, T, k) be a k-MSS instance where S = (s1, . . . , sl)
and T = (t1, . . . , tl).
Step 1) Apply Rules 1–6 until an irreducible instance is obtained,
or the correct answer is returned (In this case output the
correct answer). Denote the reduced instance again by
I = (G, S, T, k).
Step 2) Consider an out-neighbor u of sl.
If G \ {u} has a (k − 1)-MSS or G/(sl, u) has a k-MSS then
return YES
else
Return NO
Bounded Search Tree
Skew separators
A branching algorithm?!
The algorithm is correct since we have proved the
correctness of all reduction rules and the single branching
rule;
Step 1) as well as the construction of the new graphs takes
polynomial time.
Problem
Only the number of vertices but not the parameter k decreases
in the second branch (G/(sl, u))! This only yields a bound of
2O(|V(G)|)!
How to analyze the algorithm properly?
Bounded Search Tree
Skew separators
Analysis of the algorithm
Proposition (1)
Let G be an irreducible graph and u an out-neighbor of sl. Then
MinCutG(sl, T) < MinCutG/(sl ,u)(sl, T).
Proof:
An (sl, T)-cut in G/(sl, u) is an (sl, T)-cut in G that does not
contain u, but every minimum (sl, T)-cut in G contains u.
Idea
Therefore, after choosing the second branch at least k times,
MinCut(sl, T) > k and NO may be returned.
How to turn this Idea into a proper proof?
Bounded Search Tree
Skew separators
Analysis of the algorithm
Idea:
Take 2k − m instead of just k as the parameter where
m = m(G, S, T) = MinCutG(sl, T). Then do induction over
2k − m as normal.
Proposition (2)
For an irreducible instance I = (G, S, T, k) both branching
instances Ii = (Gi, S, T, ki) have 2ki − mi < 2k − m where
mi = m(Gi, S, T).
Bounded Search Tree
Skew separators
Analysis of the algorithm
Proposition (2)
For an irreducible instance I = (G, S, T, k) both branching
instances Ii = (Gi, S, T, ki) have 2ki − mi < 2k − m where
mi = m(Gi, S, T).
Proof:
In the first case G1 = G \ {u} and k1 = k − 1. Furthermore, by
deleting u from G MinCut(sl, T) decreases by at most 1.
Hence, 2k1 − m1 ≤ 2(k − 1) − (m − 1) = 2k − m − 1 < 2k − m.
In the second case G2 = G/(sl, u) and k2 = k and by
Proposition (1) m(G, S, T) < m(G2, S, T). Hence,
2k2 − m2 ≤ 2k − (m + 1) < 2k − m.
Bounded Search Tree
Skew separators
Analysis of the algorithm
Proposition (3)
For every reduction rule (1–6) that reduces (G, S, T, k) to
(G , S , T , k ) it holds that 2k − m ≤ 2k − m.
Proof:
Rules (1), (4) and (5) terminate and need not be considered.
Rule (2) (delete {sl, tl}) only applies if m = 0 and does not
change k.
Rule (3) (delete a vertex that must be in the MSS) decreases k
by 1 and m by at most 1.
Rule (6) (contract an arc out of sl) does not change k and m by
definition.
Bounded Search Tree
Skew separators
Analysis of the algorithm
Theorem
The branching algorithm for k-MSS gives a search tree with at
most 4k leaves.
Proof:
We show that the search tree has at most 22k−m leaves using
induction over 2k − m.
IB: 2k − m ≤ 0. We show that in this case one of the reduction
rules (1)–(6) apply. Because these rules do not increase
2k − m (Proposition 3) this shows that the algorithm terminates
without branching!
Case 1. (k > 0) Then m ≥ 2k > k. Hence, rule (4) applies.
Case 2. (m = 0 and l ≥ 2) Then rule (2) applies.
Case 3. (m = 0 and l = 1) Then rule (5) applies.
Bounded Search Tree
Skew separators
Analysis of the algorithm
Theorem
The branching algorithm for k-MSS gives a search tree with at
most 4k leaves.
Proof:
IS: 2k − m > 0.
Because the reduction rules do not increase 2k − m it suffices
to proof the statement for irreducible G. By Proposition (2) both
branching instances G1 and G2 have parameter strictly smaller
than 2k − m and so by induction the number of leaves is at
most:
22k−m−1 + 22k−m−1 = 22k−m
Bounded Search Tree
Vertex Coloring – a none standard parameterization
Outline
1 Bounded Search Tree
Skew separators
Vertex Coloring – a none standard parameterization
An alternative way of choosing the parameter
Bounded Search Tree – Summary
Bounded Search Tree
Vertex Coloring – a none standard parameterization
Definitions
Let G be an undirected graph and k a natural number.
k-Coloring
A proper k-vertex coloring or k-coloring of G is a function
α : V(G) → {1, . . . , k} such that for all {u, v} ∈ E(G) it holds
that α(u) = α(v).
Chromatic Number
The chromatic number (χ(G)) of G is the minimum number k
such that G admits a k-coloring.
k-COLORABILITY
Input: An undirected graph G and a natural number k.
Question: Is χ(G) ≤ k?
Bounded Search Tree
Vertex Coloring – a none standard parameterization
Definitions
k-COLORABILITY
Input: An undirected graph G and a natural number k.
Question: Is χ(G) ≤ k?
Proposition
k-Colorability is NP-hard even for k = 3.
Hence, choosing k as a parameter is hopeless, however, there
are some graph classes for which the problem is easy, i.e.,
solvable in polynomial time!
Bounded Search Tree
Vertex Coloring – a none standard parameterization
Chordal Graphs
Definition
A graph G is chordal if the vertices can be ordered v1, . . . , vn
such that the neighbors of vi in {vi+1, . . . , vn} form a clique.
Such an ordering is called a (perfect) elimination order.
Some Facts about chordal graphs:
It can be decided in linear time whether a graph G is
chordal and if so an elimination ordering witnessing this
can also be found in linear time.
If G is chordal then G \ {v} is also chordal for every
v ∈ V(G).
Bounded Search Tree
Vertex Coloring – a none standard parameterization
Chordal Graphs
Alternative Characterization
A graph G is chordal if it contains no induced cycles of length at
least 4.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
Chordal Graphs and Colorings
Theorem
χ(G) can be computed in polynomial time if G is chordal.
Proof:
First construct an elimination ordering v1, . . . , vn. This can e.g.
be achieved by choosing any vertex whose neighborhood
induces a clique and then deleting this vertex from G, etc. .
Color the vertices vi greedily in reverse order, by always
assigning the lowest color that is not used for any vj ∈ N(vi)
with j > i.
This yields a proper k-coloring for some k. Furthermore, if at
some step the color k is used for a vertex vi, then G contains a
clique on at least k vertices (consisting of vi and its higher
numbered neighbors), hence, k ≤ χ(G) ≤ k and χ(G) = k.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
Chordal Completion
Definition
The chordal completion number of a graph G is the minimum
number of edges needed to make G chordal.
Question: Can we parameterize k-coloring by the chordal
completion number?
Answer: No, because the chordal completion number can not
be computed in polynomial time!
However, what happens if we restrict the input to graphs that
can be made chordal by adding at most l edges?
Bounded Search Tree
Vertex Coloring – a none standard parameterization
l-k-Coloring
This leads us to the following problem:
l-k-Colorability Parameter: l
Input: 2 natural numbers l and k and a graph G that can be
made chordal by adding at most l edges.
Question: Is χ(G) ≤ k?
In order to solve this problem we need to be able to:
(1) Find a set A of at most l edges whose addition makes G
chordal in FPT time with respect to l.
(2) Given A of size at most l decide k-Colorability in FPT time,
again with respect to l.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
l-k-Coloring
Hence, we need to be able to solve the following two
parameterized problems in FPT time:
k-CHORDAL COMPLETION Parameter: k
Input: A graph G and a natural number k.
Question: Compute a set A of at most k edges s.t. the graph
(V(G), E(G) ∪ A) is chordal, if no such set exists answer NO.
l-CHORDAL-SUPERGRAPH-k-COLORABILITY (l-CS-k-COL)
Input: A graph G, a set A ⊆ [V(G)]2 \ E(G), and natural
number k.
Parameter: l = |A|
Question: Is χ(G) ≤ k?
Bounded Search Tree
Vertex Coloring – a none standard parameterization
Chordal Completion
k-CHORDAL COMPLETION Parameter: k
Input: A graph G and a natural number k.
Question: Compute a set A of at most k edges s.t. the graph
(V(G), E(G) ∪ A) is chordal, if no such set exists answer NO.
Theorem
k-Chordal Completion is fixed-parameter tractable, i.e., it can
be solved in time O∗(4k ) via a simple branching algorithm.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
l-CHORDAL-SUPERGRAPH-k-COLORABILITY
Hence, we are left with designing an FPT algorithm for the
following problem.
l-CHORDAL-SUPERGRAPH-k-COLORABILITY (l-CS-k-COL)
Input: A graph G, a set A ⊆ [V(G)]2 \ E(G), and natural
number k.
Parameter: l = |A|
Question: Is χ(G) ≤ k?
Bounded Search Tree
Vertex Coloring – a none standard parameterization
l-CHORDAL-SUPERGRAPH-k-COLORABILITY
Let G be a graph and {u, v} ∈ E(G).
Definition
G/{u, v} is the graph obtained from G after contracting the
edge {u, v} into a new vertex, i.e., G/{u, v} has vertex set
(V(G) \ {u, v}) ∪ {n} and edge set
{ {x, y} ∈ [V(G) \ {u, v}]2 : {x, y} ∈ E(G) }∪
{ {x, n} : x ∈ V(G) \ {u, v} and
({x, u} ∈ E(G) or {x, v} ∈ E(G)) }.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
l-CHORDAL-SUPERGRAPH-k-COLORABILITY
Let G be a graph and u, v ∈ V(G).
Definition
G ⊕ {u, v} is the graph obtained from G after adding an edge
between u and v, i.e., G ⊕ {u, v} has vertex set V(G) and edge
set E(G) ∪ {u, v}.
Definition
G ⊕/ {u, v} is the graph (G ⊕ {u, v})/{u, v}.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
l-CHORDAL-SUPERGRAPH-k-COLORABILITY
The following observation follows immediately from the
characterization of chordal graphs via long induced cycles.
Observation
If G is chordal then the graph G obtained from G by contracting
an edge is also chordal.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
A branching rule
Theorem (1)
Let G be a spanning subgraph of a chordal graph H and
{u, v} ∈ E(H) \ E(G). Then G has a k-coloring iff either
G ⊕ {u, v} has a k-coloring or G ⊕/ {u, v} has a k-coloring.
Proof:
Let α be a k-coloring of G. If α(u) = α(v) then α is also a
k-coloring of G ⊕ {u, v}. Otherwise, setting β(n) = α(u) = α(v)
and β(x) = α(x) for all x = n gives a k-coloring β of
G ⊕/ {u, v}.
For the reverse direction first note that a k-coloring of
G ⊕ {u, v} is also a k-coloring of G. Furthermore, a k-coloring
α of G ⊕/ {u, v} gives a k-coloring β of G as follows:
β(u) = β(v) = α(n) and β(x) = α(x) for all other x.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
A branching rule
Let (G, H, k) be a l-CS-k-COL instance with parameter
l = |E(H)| − |E(G)| and {u, v} ∈ E(G).
Observation (1)
Then (G ⊕ {u, v}, H, k) is l-CS-k-COL instance with parameter
|E(H)| − |E(G ⊕ {u, v})| = l − 1.
Observation (2)
Then (G ⊕/ {u, v}, H/{u, v}, k) is l-CS-k-COL instance with
parameter |E(H/{u, v})| − |E(G ⊕/ {u, v})| = l − 1.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
A branching algorithm
Theorem
The k colorability of a l-CS-k-COL instance (G, H, k) can be
decided with a branching algorithm that yields a search tree
with at most 2l leaves where l = |E(H)| − |E(G)|.
Proof:
By induction over l. If l = 0 then G is chordal and k-colorability
can be decided in polynomial time. Hence, the search tree has
only 2l = 20 = 1 node.
Bounded Search Tree
Vertex Coloring – a none standard parameterization
A branching algorithm
Theorem
The k colorability of a l-CS-k-COL instance (G, H, k) can be
decided with a branching algorithm that yields a search tree
with at most 2l leaves where l = |E(H)| − |E(G)|.
Proof, continued:
If l > 0 then we can choose an edge {u, v} ∈ E(H) \ E(G).
Using Theorem (1) we obtain that G is k-colorable iff either
G ⊕ {u, v} is k-colorable or G ⊕/ {u, v} is k-colorable. Because
of Observations (1) and (2) we obtain instances of l-CS-k-COL
with parameter ≤ l − 1 which by the induction hypothesis can
be decided with a search tree with at most 2l−1 leaves. Hence,
the search tree has at most 2l−1 + 2l−1 = 2l leaves.
Bounded Search Tree
An alternative way of choosing the parameter
Outline
1 Bounded Search Tree
Skew separators
Vertex Coloring – a none standard parameterization
An alternative way of choosing the parameter
Bounded Search Tree – Summary
Bounded Search Tree
An alternative way of choosing the parameter
Idea:
Take an NP-hard problem and a class of instances for which the
problem can be solved in polynomial time. Choose a parameter
that expresses “how close’ a particular instance is to this class,
i.e., the parameter expresses the “distance to triviality”.
To obtain an FPT algorithm for the NP-hard problem
parameterized by this “distance to triviality” you need to:
Restrict the input instances to those that are close to
triviality.
Find an FPT algorithm to compute the difference to
triviality.
Find an FPT algorithm that given the distance to triviality
solves your problem.
Bounded Search Tree
An alternative way of choosing the parameter
Examples
Example 1)
For a CNF formula F the deficiency is the difference between
the number of clauses and the number of variables. The
maximum deficiency δ∗(F) is the maximum deficiency over all
subformulas of F. Then:
formulas F with δ∗(F) = 0 are satisfiable.
An FPT algorithm for satisfiability exists for the parameter
δ∗.
Bounded Search Tree
An alternative way of choosing the parameter
Examples
Example 2)
Many graph problems are easy on trees. Later we will see a
parameter called treewidth that expresses how close a graph is
to being a tree. Almost every problem has an FPT algorithm
parameterized by treewidth.
Bounded Search Tree
An alternative way of choosing the parameter
Examples
Example 3)
Take the satisfiability problem of CNF formulas. There exists a
number of classes of formulas for which it becomes tractable,
such as, 2-CNF, HORN, 0-VALID, q-HORN etc. . Now if you can
easily (in FPT time) find a set B of variables of the formula F
such that the reduced formula F[τ] is in such a class for every
truth-assignment τ of the variables in B, then you can decide
the satisfiability of F in time O∗(2|B|) – just go over all 2|B| truth
assignments of the variables in B and decide whether F[τ] is
satisfiable. Such a set B is called a C-strong backdoor set for
some tractable class of formulas C.
Bounded Search Tree
Bounded Search Tree – Summary
Outline
1 Bounded Search Tree
Skew separators
Vertex Coloring – a none standard parameterization
An alternative way of choosing the parameter
Bounded Search Tree – Summary
Bounded Search Tree
Bounded Search Tree – Summary
Bounded Search Trees – Summary
For bounded search trees, both the node degrees (number
of branching cases) and the maximum depth should be
bounded by a function of k, to obtain an FPT algorithm.
Bounding the depth can often be done by considering the
parameter, but sometimes a new parameter needs to be
defined.
Many of the fastest FPT algorithms are branching
algorithms, using elaborate case distinctions. Analyzing
these can be done with branching vectors.