Fixed-Parameter Algorithms, IA166
Sebastian Ordyniak
Faculty of Informatics
Masaryk University Brno
Spring Semester 2013
Iterative Compression
Directed Feedback Vertex Set
Outline
1 Iterative Compression
Directed Feedback Vertex Set
Iterative Compression
Directed Feedback Vertex Set
Iterative Compression
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
k-DIRECTED FEEDBACK VERTEX SET Parameter: k
Input: A digraph D and an integer k.
Question: Is there a set S ⊆ V(D) with |S| ≤ k and D \ S is a
DAG, i.e., a directed acyclic graph?
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Using the sequence Di := D[v1, . . . , vi] for an arbitrary ordering
v1, . . . , v|V(D)| of the vertices of D we obtain:
(1) S1 := ∅ is a k-DFVS for D1.
(2) If Si is a k-DFVS for Di then Si+1 := Si ∪ {vi+1} is a
(k + 1)-DFVS for Di+1.
(3) If Di has no k-DFVS then D has no k-DFVS.
(4) FPT-algorithm for compression version????
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Using the sequence Di := D[v1, . . . , vi] for an arbitrary ordering
v1, . . . , v|V(D)| of the vertices of D we obtain:
(1) S1 := ∅ is a k-DFVS for D1.
(2) If Si is a k-DFVS for Di then Si+1 := Si ∪ {vi+1} is a
(k + 1)-DFVS for Di+1.
(3) If Di has no k-DFVS then D has no k-DFVS.
(4) FPT-algorithm for compression version????
Hence, we only need to find an FPT-algorithm for the
compression version of the problem!
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Answer
Again we guess the intersection of S with an optimal solution.
There are 2k+1 such guesses and for each guess we have to
solve an instance of k-S-DISJOINT DIRECTED FEEDBACK
VERTEX SET defined below.
k-S-DISJOINT DIRECTED FEEDBACK VERTEX SET Parameter:
|S|
Input: A digraph D , and a DFVS S of D.
Question: Is there a (|S| − 1)-DFVS for D that is disjoint from
S?
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
k-S-DISJOINT FEEDBACK VERTEX SET Parameter: |S|
Input: A graph D , and a FVS S of D.
Question: Is there a (|S| − 1)-FVS for D that is disjoint from S?
Problem
We need a novel approach here as the kernelization approach
used for k-S-DFVS fails!
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Topological Ordering
The vertices of a DAG, i.e., directed acyclic graph, can be
ordered v1, . . . , vn such that for every 1 ≤ i < j ≤ n, there is no
arc from the vertex vj to the vertex vi. Such an ordering is often
called a topological ordering and can be found in polynomial
time.
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Reduction of k-S-DDFVS to the k-SKEW SEPARATOR
PROBLEM.
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?
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Definition
Let (D, S, k) be an instance of k-S-DDFVS and let
σ : {1, . . . , k + 1} → S be a bijective function (a numbering of
S). We define the graph D(σ) to be the graph obtained from
D \ S and for every 1 ≤ i ≤ k + 1:
adding the vertices si and ti and
for every out-neighbor v of σ(i) adding an arc (si, v), and
for every in-neighbor v of σ(i) adding an arc (v, ti)
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Lemma
S ⊆ V \ S is a k-S-DDFVS iff there is a numbering σ of S such
that S is a k-Skew-separator for D(σ).
Proof:
(→) Let S be a k-S-DDFVS for D. Then D \ S is acyclic and
admits a topological ordering v1, . . . , vm.
All vertices of S are part of D \ S . Hence, we can use the
ordering to define a numbering σ of S such that for all j < i, σ(j)
is not reachable from σ(i).
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Lemma
S ⊆ V \ S is a k-S-DDFVS iff there is a numbering σ of S such
that S is a k-Skew-separator for D(σ).
Proof, continued:
Consider D(σ) and suppose that D(σ) \ S contains an
(si, tj)-path for j ≤ i.
If j < i this gives a (σ(i), σ(j))-path in D \ S contradicting the
choice of σ.
If j = i, this gives a cycle in G \ S (containing σ(i)), a
contradiction.
Hence, S is a Skew-Separator for D(σ).
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Lemma
S ⊆ V \ S is a k-S-DDFVS iff there is a numbering σ of S such
that S is a k-Skew-separator for D(σ).
Proof, continued:
(←) Let S be a k-Skew-Separator for D(σ) and suppose that
G \ S contains a cycle C.
Because S is a DFVS for D, C contains at least one vertex from
S.
If C contains exactly one vertex σ(i) from S, then C
corresponds to an (si, ti)-path in D(σ) \ S , a contradiction.
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Lemma
S ⊆ V \ S is a k-S-DDFVS iff there is a numbering σ of S such
that S is a k-Skew-separator for D(σ).
Proof, continued:
If C contains l ≥ 2 vertices from S, then let
σ(i0), σ(i1), . . . , σ(il−1) be the order of those vertices in C. Note
that ix and iy are distinct when x = y. Hence, there is an x such
that ix > ix+1 mod l. Let i = ix and j = ix+1 mod l.
The subpath of C from σ(i) to σ(j) corresponds to an
(si, tj)-path in D(σ) \ S with j < i, a contradiction.
Iterative Compression
Directed Feedback Vertex Set
Example: Directed Feedback Vertex Set
Recall:
k-MINIMUM SKEW SEPARATOR can be solved in time 4k nO(1).
Corollary
k-S-DDFVS can be solved in time (k + 1)!4k nO(1).
Hence, the combined parameter function for k-DFVS is:
k
l=0
k+1
l+1 (l + 1)!4l =
k
l=0
(k+1)!
(k−l)! 4l < (k + 1)!(k + 1)4k
Theorem
k-S-DFVS can be solved in time O∗(4k (k + 1)!).