Directed Feedback Vertex Set Problem is FPT ⋆
Jianer Chen1
, Yang Liu1
and Songjian Lu1
Department of Computer Science
Texas A&M University
College Station, TX 77843, USA
{chen,yangliu,sjlu}@cs.tamu.edu
Abstract. To decide if the parameterized feedback vertex set
problem in directed graph is fixed-parameter tractable is a long standing
open problem. In this paper, we prove that the parameterized feedback
vertex set in directed graph is fixed-parameter tractable and
give the first FPT algorithm of running time O((1.48k)k
nO(1)
) for it. As
the feedback arc set problem in directed graph can be transformed to
a feedback vertex set problem in directed graph, hence we also show
that the parameterized feedback arc set problem can be solved in
time of O((1.48k)k
nO(1)
).
Keywords. directed feedback vertex set problem, parameterized algorithm,
fixed-parameter tractability, network flow
1 Introduction
The feedback vertex set problem is defined as: given a graph G = (V, E),
find a subset F in the graph such that G − F is acyclic. We usually call F a
feedback vertex set of G, or an FVS of G. The graph G can be undirected or
directed. If we want to find an FVS with minimum size or with a size bounded
by k which we call it parameterized feedback vertex set problem, the
problem is NP-complete in both directed and undirected graph [15]. The parameterized
feedback vertex set problem in undirected graph has been
proved to be fixed-parameter tractable (FPT) [3,8] long time ago, i.e. the running
time of the algorithm is bounded by f(k)nO(1)
, where f(k) is a function
that depends only on k. But for the parameterized feedback vertex set
problem in directed graph, the problem remains open.
The feedback vertex set problem, especially in directed graph, has important
applications in Database System [14] and Operating System [27] to solve
deadlock problems, such as the deadlock recovery in operation systems [27], in
which a deadlock is presented by a cycle in a system resource-allocation graph G.
Therefore, in order to recover from deadlocks, we need to abort a set of processes
in the system, i.e., to remove a set of vertices in the directed graph G, so that
all cycles in G are broken. Equivalently, we need to find an FVS in G.
⋆
This work was supported in part by the National Science Foundation under the
Grants CCR-0311590 and CCF-0430683.
Dagstuhl Seminar Proceedings 07281
Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs
http://drops.dagstuhl.de/opus/volltexte/2007/1236
2 J. Chen, Y. Liu, S. Lu
When the graph G is undirected, there are considerable results about the
feedback vertex set problem, such as there are exact algorithms of finding
a minimum FVS in a graph on n vertices in time O(1.9053n
) [26] and in
time O(1.7548n
) [13]. There is also a polynomial time 2-approximation algorithm
for the minimum feedback vertex set problem [1]. Bodlaender [3],
Downey and Fellows [8] gave the first parameterized algorithms of running
time O(17k4
!nO(1)
) for the parameterized feedback vertex set problem
in undirected graph. Since then a chain of dramatic improvements was obtained
by different researchers, such as an algorithm with a time complexity
of O((2k + 1)k
n2
) by Downey and Fellows [9], of O(max{12k
, (4 log k)k
}n2.376
)
by Raman et al.[21], of O((2 log k + 2 log log k + 18)k
n2
) by Kanj et al.[19], of
O((12 log k/ log log k + 6)k
n2.376
) by Raman et al.[22], of O((37.7)k
n2
) by Guo
et al.[16] and of O((10.6)k
n3
) by Dehne et al.[6]. The current best result has a
time complexity of O(5k
nO(1)
) by Chen et al. [5].
In directed graph, the feedback vertex set problem becomes harder.
There are only limit progresses for it, since Karp [20] proved that to find an
FVS of size bounded by k in directed graph is NP-complete in 1972. No exact
algorithms with running time of O(cn
nO(1)
), where c < 2, and no polynomial
time approximation algorithms with constant ratio have been found
(there is an excellent polynomial time approximation algorithm with a ratio
of O(log τ∗
log log τ∗
) [11], where τ∗
is the size of the minimum feedback vertex
set). For the parameterized feedback vertex set problem in directed
graph, all current achievements only fall in some special directed graphs, such as
in the tournament graph, while the problem in general directed graph becomes
a long-standing open problem [6,7,9,10,16,17,18,19,22,23,24]. The tournament
graph is a directed graph that there is exact one arc between every pair of vertices
in the graph. As there is always a cycle of size 3 in the tournament graph
if there are any cycles in the graph, it is trivial to obtain an FPT algorithm of
running time O(3k
nO(1)
). Some other improvements for the feedback vertex
set problem in tournament graph have a time complexity of O(2.5k
nO(1)
) [28],
of O(2.42k
nO(1)
) [24], of O(2.18k
nO(1)
) [12] and the current best algorithm has
a running time of O(2k
nO(1)
) [7]. By the way, Raman and Saurabh gave an FPT
algorithm of running time O((c k/e)k
nO(1)
) [23] for the parameter feedback
arc set (FAS) problem in tournament graph, which removes a subset of
at most k edges to make the graph acyclic.
In this paper, we solve this well-known open problem in FPT world: is the
parameterized feedback vertex set problem in general directed graph
fixed-parameter tractable? Our answer is “Yes”, the parameterized feedback
vertex set problem in directed graph is fixed-parameter tractable. And
we give an FPT algorithm of running time O((1.48k)k
nO(1)
) for it. Our idea is:
first, using O(k!) time to transform the parameterized feedback vertex
set problem in directed graph into constrained multicut problem through
dag-bipartition fvs, ordered dag-bipartition fvs problems (see Section
3 of the paper). Then design an FPT algorithm for the constrained multicut
problem. Hence, obtain the first FPT algorithm for the parameterized
Directed Feedback Vertex Set Problem is FPT 3
feedback vertex set problem in directed graph. As solving the parameter
feedback arc set problem in directed graph D = (V, A) is equivalent to solving
a parameter feedback vertex set problem in D’s line graph [11], we
also solve the parameter feedback arc set in O((1.48k)k
nO(1)
) time.
The organization of our paper is as following: In section 2, we introduce an
extended form of the Menger’s Theorem in directed graph, which we will use
it in Section 4. In section 3, we define the dag-bipartition fvs, ordered
dag-bipartition fvs and constrained multicut problems. In section 4, we
give the FPT algorithm for the constrained multicut problem. In section 5,
we give the FPT algorithms for the dag-bipartition fvs, the parameterized
feedback vertex set and the parameterized feedback arc set problems.
2 The minimum V-cut from subset T1 to subset T2 in a
digraph
In this section, we introduce an extended form of Menger’s theorem. Let us start
with some terminology.
Let D = (V, A) be a directed graph and let u and v be two vertices in D. A
path from u to v is a simple path in D that begins from u (has only outgoing
arc of the path) and ends at v (has only incoming arc of the path). Let T and u
be a subset and a vertex of D respectively, a path from u to T is a path from u
to a vertex in T (a path from T to u is a path from a vertex in T to u). For two
subsets T1 and T2 in D, a path from T1 to T2 is a path from a vertex in T1 to a
vertex in T2. Two paths are internally disjoint if there exists no vertex that is
an internal vertex for both paths.
Given a directed graph D = (V, A), a subset S is a V-cut from vertex u to
vertex v (a V-cut from subset T1 to subset T2) if no path exits from u to v (from
T1 to T2) in the subgraph D − S.
In a directed graph D = (V, A), we use (u, v) to denote an arc from u to v.
When we say u is adjacent to v (or v is a neighbor of u), we mean (u, v) is an
arc in A. Let V ′
be a subset of V , we denote by D(V ′
) the subgraph of D that
is induced by the vertex set V ′
Finally, for a subset T in D = (V, A), by merging T (into a single vertex), we
mean the operation that first deletes all vertices in T then creates a new vertex
w and makes (w, u)/(u, w) be an outgoing/incoming arc of w if there is a vertex
v in T such that (v, u)/(u, v) is an arc in D.
The following directed vertex form of Menger’s Theorem and its proof can
be found in [4].
Proposition 1. [4] (The Directed Vertex Form of Menger’s Theorem) Let s
and t be two distinct vertices of a directed graph D such that s is not adjacent
to v, then the maximum number of internally disjoint directed paths from s to t
in D equals the size of a minimum V-cut from s to t in D.
In Lemma 1, we generalize Proposition 1 from the case of two vertices to the
case of two vertex subsets.
4 J. Chen, Y. Liu, S. Lu
Lemma 1. Let T1 and T2 be two disjoint vertex subsets in a directed graph D
such that no vertex in T1 is adjacent to a vertex in T2. Then the maximum
number h of internally disjoint paths from T1 to T2 in D is equal to the size of
a minimum V-cut from T1 to T2 in D. Moreover, for any set π of h internally
disjoint paths from T1 to T2 in D, every minimum V-cut from T1 to T2 in D
contains exact on vertex in each of paths in π.
Proof. Let D′
be the graph obtained from the graph D by merging the two
vertex subsets T1 and T2 into two vertices t1 and t2, respectively. Note that t1
is not adjacent to t2 in D′
.
By the definition of the merge operation, it is easy to verify that a vertex
subset S is a V-cut from the vertex subset T1 to the vertex subset T2 in the
graph D if and only if S is a V-cut from the vertex t1 to the vertex t2 in the
graph D′
. In particular, the size of a minimum V-cut from T1 to T2 in D is equal
to the size of a minimum V-cut from t1 to t2 in D′
. Moreover, it is also easy
to verify that for any integer h′
, from a set of h′
internally disjoint paths from
T1 to T2 in D, we can construct a set of h′
internally disjoint paths from t1 to
t2 in D′
, and vice versa. Therefore, the maximum number of internally disjoint
paths from T1 to T2 in D is equal to the maximum number of internal disjoint
paths from t1 to t2 in D′
. Now the first part of the lemma follows by applying
Proposition 1 to the graph D′
.
To prove the second part of the lemma, let S be a minimum V-cut, of size
h, from T1 to T2 in D, and let π be a set of h internally disjoint paths from T1
to T2. The vertex set S must contain at least one vertex from each of the paths
in π: otherwise there would be a path from T1 to T2 in D − S, contradicting
the assumption that S is a V-cut from T1 to T2. Moreover, the set S cannot
contain more than one vertex in any path in π: otherwise S would not be able
to contain at least one vertex for each of the paths in π (note that the paths in
π are internally disjoint). ⊓⊔
Lemma 1 provides an efficient algorithm that constructs the maximum number
of internally disjoint paths and a minimum-size V-cut from a vertex subset
to another vertex subset.
Lemma 2. Let T1 and T2 be two disjoint vertex subsets in a directed graph
D = (V, A) such that no vertex in T1 is adjacent to a vertex in T2. Then in time
O((|V | + |A|)k), we can decide if the size h of a minimum V-cut from T1 to T2
is bounded by k, and in case h ≤ k, construct h internally disjoint paths from
T1 to T2.
Proof. Let D′
be the graph obtained from the graph D by merging the two
vertex subsets T1 and T2 into two vertices t1 and t2, respectively. As discussed
in the proof of Lemma 1, it suffices to show how to decide if the size h of a
minimum V-cut from t1 to t2 in D′
is bounded by k, and in case h ≤ k, how to
construct h internally disjoint paths from t1 to t2.
This can be done based on the standard approach to the maximum t1-t2
flow problem [4]. For this, we modify the new directed graph D′
by replacing
Directed Feedback Vertex Set Problem is FPT 5
each vertex u (except the vertices t1 and t2) by two vertices u1 and u2 with
an arc from u1 to u2, connecting all u’s incoming arcs to the vertex u1 and
connecting all u’s outgoing arcs to the vertex u2. Finally we set all edges to have
capacity 1. Let the resulting flow graph be D′′
.
Applying Ford-Fulkerson’s standard approach using augmenting paths, in
time O((|V | + |A|)k), we can either construct a t1-t2 flow of value larger than k
in D′′
, or end up with a maximum t1-t2 flow of value h bounded by k. In the
former case, we conclude that the size of a minimum V-cut from t1 to t2 in D′
is
larger than k, which implies that the size of a minimum V-cut from T1 to T2 in
D is larger than k. In the latter case, h internally disjoint paths from t1 and t2 in
D′
can be easily constructed from the maximum t1-t2 flow of value h in D′′
, from
which h internally disjoint paths from T1 to T2 in D can be constructed. ⊓⊔
3 dag-bipartition fvs, ordered dag-bipartition fvs and
constrained multicut problems
Before we introduce our algorithm for the FVS problem in directed graph, we
introduce several problems that are closely related to the FVS problem in directed
graphs. We also start with some terminology. Given a directed graph
D = (V, A) and two subsets V1, V2 of V , if V1 ∪ V2 = V , V1 ∩ V2 = ∅ and both
induced subgraphs D(V1) and D(V2) are directed acyclic graphs, then we say
that the pair (V1, V2) is a DAG bipartition of the directed graph D = (V, A). In
the DAG bipartition (V1, V2) of the directed graph D = (V, A), if forder : V2 →
{1, 2, . . ., |V2|} is a topological order of V2 such that no arcs from u to v for any
forder(u) ≥ forder(v), then we say (V1, V2, forder) is an ordered DAG bipartition
of the directed graph D = (V, A). Now we define these problems:
dag-bipartition fvs: given a directed graph D = (V, A), a DAG bipartition
(V1, V2) of D, and an integer k, either find an FVS of size bounded
by k in V1 for the directed graph D, or report that no such an FVS
exists.
ordered dag-bipartition fvs: given a directed graph D = (V, A), an
ordered DAG bipartition (V1, V2, forder) of D, and an integer k, either
find a subset F (also called FVS) of size bounded by k in V1 such that
there exist no paths from u to v for any u, v in V2 and forder(u) ≥
forder(v) in the induced subgraph D(V − F), or report that no such an
F exists.
constrained multicut: given a directed acyclic graph D = (V, A), 2l
pairwise disjoint subsets (called terminal sets) S1, S2, . . . , Sl, T1, T2, . . . , Tl
of V and an integer k, we suppose that D satisfy: 1) any vertex in Si for
1 ≤ i < l has no incoming arcs; 2) any vertex in Ti for 1 ≤ i ≤ l has no
outgoing arcs. Either find a subset S of V (called separator) that has no
elements come from any terminal sets and includes at least one vertex
of any path from Sj to Ti for j ≥ i, or report no such an S exists.
6 J. Chen, Y. Liu, S. Lu
We denote the instance of the dag-bipartition fvs problem as (D, V1, V2, k),
the instance of the ordered dag-bipartition fvs problem as (D, V1, V2, forder,
k) and the instance of the constrained multicut problem as (D, (S1, . . . , Sl),
(T1, . . . , Tl), k).
For the dag-bipartition fvs problem and the ordered dag-bipartition
fvs problem, they have the following relation.
Theorem 1. Given an instance (D, V1, V2, k) of the dag-bipartition fvs problem,
then (D, V1, V2, k) has an FVS of size bounded by k if and only if there exists
an instance (D, V1, V2, forder, k) of the ordered dag-bipartition fvs problem
that also has an FVS of size bounded by k.
Proof. If an instance (D, V1, V2, forder, k) of the ordered dag-bipartition fvs
problem has an FVS F of size bounded by k, then there exist no paths from
u to v in the induced subgraph D(V1 ∪ V2 − F) for any u, v in V2 that satisfy
forder(u) ≥ forder(v). So if the induced subgraph D(V1 ∪V2 −F) has a cycle, this
cycle can not include any vertex from V2. But as the induced subgraph D(V1)
is a directed acyclic graph, no cycle can include all vertices just from V1. Thus
the induced subgraph D(V1 ∪ V2 − F) has no cycle, i.e. F ⊆ V1 is an FVS for
the directed graph D. Therefore F is an FVS for the instance (D, V1, V2, k) of
the dag-bipartition fvs problem.
For the other direction, if the instance (D, V1, V2, k) of the dag-bipartition
fvs problem has an FVS F of size bound by k, then F ⊆ V1 is also an FVS
for the directed graph D. So D(V1 ∪ V2 − F) is a directed acyclic graph. Let
(v1, v2, . . . v|V1∪V2−F |) be a topological order of the set V1 ∪ V2 − F such that no
paths from vj to vi for j ≥ i. If we use this order to define the order function
forder for the subset V2, then it is obvious that there exist no paths from u to v
in the induced graph D(V1 ∪ V2 − F) for any u, v in V2 that satisfy forder(u) ≥
forder(v) and there exist no arcs from u to v for any u, v in V2 that satisfy
forder(u) ≥ forder(v), i.e. F is an FVS of size bounded by k for the instance
(D, V1, V2, forder, k) of the ordered dag-bipartition fvs problem. ⊓⊔
Given an instance I = (D, V1, V2, forder, k) of the ordered dag-bipartition
fvs problem, where V2 = {v1, v2, . . . , vl} and forder(vi) = i, we replace each
vi ∈ V2 by two vertices si and ti, connect all vi’s incoming arcs to the vertices
ti and connect all vi’s outgoing arcs to the vertex si. Then we obtain a new
directed graph D′
= (V ′
, A′
). In the new directed graph D′
= (V ′
, A′
), we let
Si = {si} and Ti = {ti} for all 1 ≤ i ≤ l, then we have the following lemma.
Lemma 3. The directed graph D′
= (V ′
, A′
) is acyclic and (D′
, (S1, . . . , Sl), (T1,
. . . , Tl), k) is an instance of the constrained multicut problem.
Proof. As both induced subgraphs D(V1) and D(V2) are acyclic, any cycle C
in graph D must contain at least one vertex in V2. Suppose vi ∈ V2 is in cycle
C, then when we create graph D′
, replace vi by si and ti and connect all vi’s
incoming arcs to the vertices ti and connect all vi’s outgoing arcs to the vertex
si. As there is no arc from ti to si, so the cycle C in D is break by si and ti in
D′
. Hence, the directed graph D′
is acyclic.
Directed Feedback Vertex Set Problem is FPT 7
In the directed acyclic graph D′
, from the operations we make si and ti.
Every si has no incoming arcs and every ti has no outgoing arcs, therefore all
Si and Ti satisfy the conditions for an instance of the constrained multicut
problem, i.e. (D′
, (S1, . . . , Sl), (T1, . . . , Tl), k) is an instance of the constrained
multicut problem. ⊓⊔
We say that the instance I′
= (D′
, (S1, . . . , Sl), (T1, . . . , Tl), k) is generated
from the instance I = (D, V1, V2, forder, k) and for the instance I′
, we have the
following result:
Theorem 2. Given an instance I = (D, V1, V2, forder, k) of the ordered dagbipartition
fvs problem, then the instance I has an FVS F of size bounded by
k if and only if the instance I′
, that is generated from I, of the constrained
multicut problem has a separator S = F of size bounded by k.
Proof. From the operations we use the instance I to generate the instance I′
, it
is obvious that the instance I has a path from vj to vi for j ≥ i if and only if the
instance I′
has a path from Sj to Ti for j ≥ i. Therefore subset F ⊆ V1 breaks
all path from vj to vi for j ≥ i in the instance I if and only if F ⊆ V1 breaks all
paths from Si to Ti in the instance I′
for j ≥ i. Thus the theorem is correct. ⊓⊔
4 Algorithm for the constrained multicut problem
Given an instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k) of the constrained multicut
problem, let Tother = l
i=1 Ti. Without loss of generality, we suppose the
size of minimum V-cut from Sl to Tother is not zero; or if the size of minimum
V-cut from Sl to Tother is zero, it is obvious that to solve the instance
(D, (S1, . . . , Sl), (T1, . . . , Tl), k), we only need to solve the instance (D, (S1, . . . ,
Sl−1), (T1, . . . , Tl−1), k). Let u be an outneighbor of Sl (i.e. u is a neighbor of
a vertex in Sl and u is not in Sl) that has no neighbor in Tother and is not in
Tother. As all terminal sets S1, . . . , Sl have no incoming arcs, hence u is not in
any terminal sets of S1, . . . , Sl, T1, . . . , Tl. Let S′
l = Sl ∪ {u}, first, we give the
following lemma:
Lemma 4. Both (D, (S1, . . . , S′
l), (T1, . . . , Tl), k) and (D − u, (S1, . . . , Sl), (T1,
. . . , Tl), k) are instances of the constrained multicut problem.
Proof. As (D, (S1, . . . , Sl), (T1, . . . , Tl), k) is an instance of the constrained
multicut problem, no Si has any incoming arc for 1 ≤ i < l and no Ti has any
outgoing arc for 1 ≤ i ≤ l. First, it is easy to verify that adding u to Sl or deleting
u from the graph D will no change the property that no Si has any incoming arc
for 1 ≤ i < l and no Ti has any outgoing arc for 1 ≤ i ≤ l. Second, it is obvious
that u is not in any terminal set. Hence, terminal sets S1, . . . , S′
l, T1, . . . , Tl are
still pairwise disjoint. Therefore the lemma is correct. ⊓⊔
Lemma 4 can make sure that the operations of adding u to Sl or delete u
from the graph D in our algorithm CMC(...) will not change the instance of the
8 J. Chen, Y. Liu, S. Lu
constrained multicut problem to the instance of other problems. For the instance
(D, (S1, . . . , S′
l), (T1, . . . , Tl), k), we have the following crucial observation
for our algorithm. Figure 1 can help you to understand our proof. In the figure,
the part under the diagonal dashed line is the part of graph D that its every
vertex x can be reached by a path that is from a vertex in Sl to x in D.
Theorem 3. If the size of the minimum V-cut from Sl to Tother is the same with
the size of the minimum V-cut from S′
l = Sl ∪ {u} to Tother, where u is a outneighbor
of Sl, then the instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k) has a separator
of size bounded by k if and only if the instance (D, (S1, . . . , S′
l), (T1, . . . , Tl), k)
has a separator of size bounded by k.
Proof. If the instance (D, (S′
1, . . . , Sl), (T1, . . . , Tl), k) has a separator S of size
bounded by k, then it is obvious that S is also a separator of the instance
(D, (S1, . . . , Sl), (T1, . . . , Tl), k).
Now we consider the other direction.
Suppose that Sm is a minimum V-cut from S′
l to Tother, then Sm is also a
V-cut from Sl to Tother. In fact, by the assumption of the theorem, Sm is also a
minimum V-cut from Sl to Tother. Let C(Sl) be the set of vertices x such that
either x ∈ Sl or there is a path form Sl to x in the induced subgraph D(V −Sm).
In particular, u ∈ C(Sl). Moreover, let C(Tother) = V − C(Sl) − Sm.
By Lemma 1, there exist |Sm| internally disjoint paths from Sl to Tother, each
contains exactly one vertex in the set Sm. Therefore, each of these |Sm| paths
is cut into two subpaths by a vertex in Sm, such that one subpath is in the
induced subgraph D(C(Sl)) and the another subpath is in the induced subgraph
D(C(Tother)). From this, we derive that there are |Sm| internally disjoint paths
from Sl to Sm in the induced subgraph D(C(Sl) ∪ Sm), each contains a distinct
vertex in the set Sm.
Let Sk be a separator of the instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k) of size
bounded by k. Define S′
k = Sk ∩ C(Sl), B = Sk ∩ Sm, and S′′
k = Sk ∩ C(Tother).
Finally, let S′
m be the set of vertices x in Sm such that there is a path from x
to Tother in the induced subgraph D(C(Tother) ∪ Sm − Sk) (see Figure 1 for an
intuitive illustration of these sets).
We first prove that |S′
k| ≥ |S′
m|.
From the fact that there are |Sm| internally disjoint paths from Sl to Sm
in the induced subgraph D(C(Sl) ∪ Sm) in which each path contains a distinct
vertex in the set Sm, we derive that there are |S′
m| internally disjoint paths from
Sl to S′
m in the induced subgraph D(C(Sl)∪S′
m). If |S′
k| < |S′
m|, then there must
be a path P1 from Sl to a vertex v′
in S′
m in the subgraph D(C(Sl)∪S′
m −S′
k) =
D(C(Sl) ∪ S′
m − Sk). Moreover, by the definition of the set S′
m, there is also a
path P2 from v′
to Tother in the induced subgraph D(C(Tother) ∪ Sm − Sk). The
concatenation of the paths P1 and P2 would give a path from Sl to Tother in
the induced subgraph D(V − Sk), which contradicts the assumption that Sk is
a separator of the instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k). Therefore, we must
have |S′
k| ≥ |S′
m|.
We then prove that the set Snew = S′
m ∪ B ∪ S′′
k does not include any vertex
in the terminal sets of S1, . . . , S′
l, T1, . . . , Tl.
Directed Feedback Vertex Set Problem is FPT 9
Sl
T2
T3
Tl
C(Tother)
SmC(Sl)
Sk
B
u
S″m
S′m
T1
S1
S2
Sl-1
S′k
S″k
Fig. 1. Decomposition of Separators
As S′′
k is a subset of the separator Sk of the instance (D, (S1, . . . , Sl), (T1, . . . ,
Tl), k), by the definition of the separator, S′′
k does not include any vertex from
terminal sets S1, . . . , Sl, T1, . . . , Tl. And u is in C(Sl), so u /∈ S′′
k . Sm is a
minimum V-cut from S′
l, that includes u, to Tother; hence S′
l ∩ Sm = ∅ and
Tother ∩ Sm = ∅. This means Sm’s subsets S′
m and B will not include any vertex
in Sl and T1, . . . , Tl. Also as any vertex x in Sm can be reached by a path
from a vertex in S′
l to x and all terminal sets S1, . . . , Sl−1 do not have incoming
arcs, so S′
m and B will not include any vertex from terminal sets S1, . . . , Sl−1.
Therefore, Snew = S′
m ∪ B ∪ S′′
k does not include any vertex in the terminal sets
of S1, . . . , S′
l, T1, . . . , Tl.
We now prove that the set Snew breaks all paths from S′
l to Ti for l ≥ i ≥ 1
and all paths from Sj to Ti for l > j ≥ i ≥ 1 in the instance (D, (S1, . . . , S′
l), (T1,
. . . , Tl), k). Suppose Snew does not break all paths that need to be break, then
there are two vertices v1 and v2 that v1 is in S′
l (i.e. j = l) or Sj, v2 is in Ti, j ≥ i
and there exists a path P from v1 to v2 in the induced subgraph D(V − Snew).
We discuss this in two possible cases.
Case 1: There is a vertex w in the path P such that w ∈ C(Sl). Because (1)
v2 is in the set Tother, (2) there is a path from Sl to w in the induced subgraph
D(C(Sl)), and (3) Sm is a V-cut from Sl to Tother, we conclude that there must
be a vertex s ∈ Sm that is also on the path P. We suppose that the subpath
P′
of P that is from s to v2 has no vertices from C(Sl) – for this we only have
to pick the last vertex s in Sm when we traverse on the path P from v1 to v2.
Then the path P′
is in the induced subgraph D(C(Tother) ∪ Sm − Snew), which
is a subgraph of the induced subgraph D(C(Tother) ∪ Sm − Sk). Now by the
definition of the set S′
m, the vertex s is in the set S′
m, thus in the set Snew.
But this is impossible because we assumed that the path P is in the induced
subgraph G(V − Snew).
10 J. Chen, Y. Liu, S. Lu
Case 2: All vertices of the path P come from the induced subgraph D(V −
Snew − C(Sl)). Then the vertex v1 can not be from the set Sl. Moreover, since
D(V − Snew − C(Sl)) is a subgraph of the induced subgraph D(V − Sk), this
implies that the path P is from Sj for j < l to Ti for j ≥ i and contains no
vertex in Sk. But this again contradicts the assumption that Sk is a separator
of the instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k).
Combining the discussions in Case 1, Case 2 and that Snew having no vertex
in any terminal sets of S1, . . . , S′
l, T1, . . . , Tl, we conclude that the set Snew is a
separator of the instance (D, (S1, . . . , S′
l), (T1, . . . , Tl), k).
Since |S′
k| ≥ |S′
m|, Sk = S′
k ∪ B ∪ S′′
k , and Snew = S′
m ∪ B ∪ S′′
k , and S′
k
does not intersect B ∪ S′′
k , we conclude that |Sk| ≥ |Snew|. In particular, if the
instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k) has the separator Sk of size bounded by
k, then the instance (D, (S1, . . . , S′
l), (T1, . . . , Tl), k) has the separator Snew of
size also bounded by k.
This completes the proof of the theorem. ⊓⊔
The proof of Theorem 3 becomes complicated partially because the vertex u
may be included in a separator for the instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k). If
we restrict that the vertex u is not in the separators for the instance (D, (S1, . . . ,
Sl), (T1, . . . , Tl), k), then a result similar to Theorem 3 can be obtained much
more easily, even without the need of the condition that the minimum V-cuts
from Sl to Tother =
l
j=1 Tj and the minimum V-cuts fromS′
l to Tother have the
same size. This is given in the following lemma. This result will also be needed
in our algorithm.
Lemma 5. Let S be a vertex subset in graph D such that S does not include the
vertex u. Then S is a separator for the instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k)
if and only if S is a separator for the instance (D, (S1, . . . , S′
l), (T1, . . . , Tl), k).
Proof. If S is a separator for the instance (D, (S1, . . . , Sl), (T1, . . . , T′
l ), k), then it
is obvious that S is also a separator for the instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k).
For the other direction, suppose that the set S is a separator for the instance
(D, (S1, . . . , Sl), (T1, . . . , Tl), k). We show that S is also a separator for the instance
(D, (S1, . . . , S′
l), (T1, . . . , Tl), k). Suppose that S is not a separator for
the instance (D, (S1, . . . , S′
l), (T1, . . . , Tl), k). Then there is a path P in G − S
from S′
l to Ti for l ≥ i ≥ 1 or form Sj to Ti for l > j ≥ i ≥ 1. The path P
must contain the vertex u (recall that S does not contain u) – otherwise the
path P in G − S would be from a Sj to Ti for l ≥ j ≥ i ≥ 1, contradicting the
assumption that S is a separator for (D, (S1, . . . , Sl), (T1, . . . , Tl), k). However,
this would imply that the path from Sl to u (recall that u is an non-terminal
neighbor of Sl) then following the path P to the terminal set Ti would give
a path in G − S from Sl to Ti, again contradicting the assumption that S is a
separator for (D, (S1, . . . , Sl), (T1, . . . , Tl), k). Therefore, S is also a separator for
the instance (D, (S1, . . . , S′
l), (T1, . . . , Tl), k). ⊓⊔
Now we present our FPT algorithm to solve the constrained multicut
problem.
Directed Feedback Vertex Set Problem is FPT 11
Algorithm CMC(D, (S1, . . . , Sl), (T1, . . . , Tl), k)
input: an instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k) of the
constrained multicut problem
output: a separator of size bounded by k for (D, (S1, . . . , Sl), (T1, . . . , Tl), k),
or report “No” (i.e., no such a separator)
1. if Sl has a neighbor in
Sl
i=1 Ti
then return “No”;
2. if Sl’s outneighbor w has a neighbor in
Sl
i=1 Ti
then return w + CMC(D − w, (S1, . . . , Sl), (T1, . . . , Tl), k − 1);
3. find the size m1 of a minimum V-cut from Sl to
Sl
i=1 Ti;
4. if m1 > k then return “No”;
5. else if (m1 = 0 and l = 1) then return ∅;
5.1 if (m1 = 0 and l > 1) then
return CMC(D, (S1, . . . , Sl−1), (T1, . . . , Tl−1), k);
6. else pick an Sl’s outneighbor u ; let S′
l = Sl ∪ {u};
6.1 if the size of a minimum V-cut from S′
l to
Sl
i=1 Ti is equal to m1
then return CMC(D, (S1, . . . , S′
l), (T1, . . . , Tl), k);
6.2 else S = u + CMC(D − u, (S1, . . . , Sl), (T1, . . . , Tl), k − 1);
if S is not “No” then return S;
6.3 else return CMC(D, (S1, . . . , S′
l), (T1, . . . , Tl), k).
Fig. 2. Algorithm for the constrained multicut problem
Theorem 4. The algorithm CMC(D, (S1, . . . , Sl), (T1, . . . , Tl), k) solves the constrained
multicut problem in time O(n3
k4k
).
Proof. We first prove the correctness of the algorithm. Let (D, (S1, . . . , Sl), (T1,
. . . , Tl), k)) be an input to the algorithm, which is an instance of the constrained
multicut problem, where D = (V, E) is a directed acyclic graph,
(S1, . . . , Sl), (T1, . . . , Tl) are two groups of ordered terminal sets, and k is the
upper bound of the size of the separator we are looking for.
If Sl has a neighbor in
l
i=1 Ti, then we have no way to separate Sl and
some Ti since all vertices in a separator are supposed to be non-terminals. Step
1 handles this case correctly.
If w that is a outneighbor of Sl has a neighbor in some Ti, then w must be in
the separator because otherwise we can not separate Sl from Ti (remember: w
is not in any terminal sets of S1, . . . , Sl, T1, . . . , Tl). Thus, we can simply include
the vertex w in the separator, and recursively find a separator of size bounded
by k − 1 for the same groups of terminal sets (S1, . . . , Sl), (T1, . . . , Tl) in the
remaining graph D − w (by Lemma 4 (D − w, (S1, . . . , Sl), (T1, . . . , Tl), k − 1)) is
12 J. Chen, Y. Liu, S. Lu
also an instance of the constrained multicut problem). This case is correctly
handled by step 2.1
Step 3 computes the size m1 of a minimum V-cut from the sets Sl to
l
j=1 Tj.
By Lemma 2, m1 can be computed in time O((|V | + |A|)k). Thus, step 3 takes
time O((|V | + |A|)k).
If m1 > k, then the size of a minimum V-cut from Sl to
l
j=1 Tj is larger
than k, which implies that even separating the set Sl from the other sets
l
j=1 Tj
requires more than k vertices. Thus, no separator of size bounded by k can exist
to separate Sj from Ti for l ≥ j ≥ i ≥ 1. This is handled by step 4.
In step 5 we handle the case m1 = 0 and l = 1, this means we do not need to
remove any vertex to separate S1 and T1, i.e. the problem is solved. Hence we
just return ∅ as a separator of size 0. And in step 5.1 m1 = 0 and l > 1 means
that there is no path from Sl to any Ti for l ≥ i ≥ 1. And as all Si for l > i ≥ 1
have no incoming arcs and all Ti for l ≥ i ≥ 1 have no outgoing arcs, we only
need to separate any path from Sj to Ti for l − 1 ≥ j ≥ i ≥ 1, i.e. we need
to solve the instance (D, (S1, . . . , Sl−1), (T1, . . . , Tl−1), k)) (note that because of
step 4, here we must have k ≥ 0. And step 5.1 repeats at most l times.).
When the algorithm reaches step 6, the following conditions hold true: (1)
k > 0 and Sl does not have any neighbor in Ti for l ≥ i (because of step 1);
(2) Sl does not have any no terminal neighbor w that has a neighbor in Ti for
l ≥ i (because of step 2); (3) 0 < m1 ≤ k (because of steps 4-5). In particular,
by condition (3), Sl must have a non-terminal neighbor u that has no neighbor
in Ti for l ≥ i.
Let m′
be the size of a minimum V-cut from the sets Sl = Sl ∪ {u}′
and
l
j=1 Tj. If m′
= m1, then by Theorem 3, the instance (D, (S1, . . . , Sl), (T1, . . . ,
Tl), k) has a separator of size bounded by k if and only if the instance (D, (S1, . . . ,
S′
l), (T1, . . . , Tl), k) has a separator of size bounded by k. In particular, as shown
in the proof of Theorem 3, a separator of size bounded by k for the instance
(D, (S1, . . . , S′
l), (T1, . . . , Tl), k) is actually also a separator for the instance (D, (S1,
. . . , Sl), (T1, . . . , Tl), k). Therefore, in this case, we can recursively work on the
instance (D, (S1, . . . , S′
l), (T1, . . . , Tl), k), as given in step 6.1 (note that step
6.1 repeats at most n times). On the other hand, if m′
= m (m′
> m),
then we simply branch on the vertex u in two cases: (1) one case includes
u in the separator (we can do it safely, for u is not in any terminal sets of
S1, . . . , Sl, T1, . . . , Tl) and recursively works on the remaining graph for a separator
of size bounded by k − 1, as given by step 6.2; and (2) the other case
excludes u from the separator thus looks for a separator that does not include u
and is of size bounded by k for the instance (D, (S1, . . . , Sl), (T1, . . . , Tl), k). By
Lemma 5, the second case is equivalent to finding a separator of size bounded
by k for the instance (D, (S1, . . . , S′
l), (T1, . . . , Tl), k). This case is thus handled
by step 6.3 (note: by Lemma 4, both (D − u, (S1, . . . , Sl), (T1, . . . , Tl), k − 1)
1
To simplify the expression, we suppose that “No” plus any vertex set gives a “No”.
Therefore, step 2 will return a “No” if CMC(D−w, (S1, . . . , Sl), (T1, . . . , Tl), k−1))
returns a “No”.
Directed Feedback Vertex Set Problem is FPT 13
and (D, (S1, . . . , S′
l), (T1, . . . , Tl), k) are instances of the constrained multicut
problem).
This completes the proof of the correctness of the algorithm. Now we analyze
the complexity of the algorithm.
The recursive execution of the algorithm can be described as a search tree
T . We first count the number of leaves in the search tree T . Note that only
steps 6.2-6.3 of the algorithm correspond to branches in the search tree T . Let
T (k, m) be the total number of leaves in the search tree T for the algorithm
CMC(D, (S1, . . . , Sl), (T1, . . . , Tl), k), where m is the size of a minimum V-cut
from the sets Sl to l
j=1 Tj. Then steps 6.2-6.3 induce the following recurrence
relation:
T (k, m) ≤ T (k − 1, m′′
) + T (k, m′
) (1)
where m′′
is the size of a minimum V-cut from Sl to l
j=1 Tj in the graph D − u
as given in step 6.2, and m′
is the size of a minimum V-cut from S′
l to
l
j=1 Tj
as given in step 6.3. Note that m − 1 ≤ m′′
≤ m because removing the vertex u
from D cannot increase the size of a minimum V-cut from Sl to
l
j=1 Tj, and can
decrease the size of a minimum V-cut from Sl to
l
j=1 Tj by at most 1. Moreover,
because the minimum V-cut from S′
l to l
j=1 Tj is not less than the minimum
V-cut Sl to
l
j=1 Tj, and because of step 6.1, the size m′
of a minimum V-cut
from S′
l to
l
j=1 Tj in step 6.3 is at least m + 1, i.e. m′
≥ m + 1. Summarizing
these, we have
m − 1 ≤ m′′
≤ m and m′
≥ m + 1 (2)
Introduce a new function T ′
such that T (k, m) = T ′
(2k − m), and let t =
2k − m. Then by Inequalities (1) and (2), the branch in step 6.2-6.3 in the
algorithm becomes
T ′
(t) ≤ T ′
(t1) + T ′
(t2)
where when t = 2k −m then t1 = 2(k −1)−m′′
≤ t−1, and t2 = 2k −m′
≤ t−1
(note that in step 2, 5 and 6.1, variable t will not increase). Our initial instance
starts with t = 2k − m ≤ 2k. In the case t = 2k − m = 0, because we also have
the conditions k ≥ m ≥ 0, we can derive m = 0 and k = 0, in this case the
algorithm can solve the instance without further branching. Therefore, we have
D′
(0) = 1. Combining all these, we derive
T (k, m) = T ′
(2k − m) ≤ 22(k+1)
= 4k+1
,
and the search tree T has at most 4k+1
leaves.
Finally, it is easy to verify that along each root-leaf path in the search tree
T , the running time of the algorithm is bounded by O(n3
k), where n is the
number of vertices in the graph. In conclusion, the running time of the algorithm
CMC(D, (S1, . . . , Sl), (T1, . . . , Tl), k) is bounded by O(n3
k4k
).
This completes the proof of the theorem. ⊓⊔
14 J. Chen, Y. Liu, S. Lu
5 Directed FVS problem is FPT
After a long and hard section for the constrained multicut problem, we come
to an easy and important part of our paper. In this section, we will give the first
FPT algorithm for the directed FVS problem. But before we do it, let us give
an FPT algorithm for the dag-bipartition fvs problem.
Theorem 5. Given an instance (D, V1, V2, k) of the dag-bipartition fvs problem,
let |V2| = l. Then in time of O(l!n3
k4k
), we can either find an FVS F of
size bounded by k for the instance, or report no such an F exists.
Proof. By Theorem 1, the instance (D, V1, V2, k) of the dag-bipartition fvs
problem has an FVS F of size bounded by k if and only if there exists at least one
instance (D, V1, V2, forder, k) of the ordered dag-bipartition fvs problem
that has an FVS of size bounded by k. As |V2| = l, we have at most l! possible
orders for the elements in V2. Hence, we need only test at most l! instances of
the ordered dag-bipartition fvs problem to know if there is one instance of
the ordered dag-bipartition fvs problem that has an FVS of size bounded
by k.
By Theorem 2, an instance I of the ordered dag-bipartition fvs problem
has an FVS F of size bounded by k if and only if the instance I′
, that is generated
from the instance I, of the constrained multicut problem has a separator
S = F of size bounded by k. Generating I′
from I takes only O(|A|) time, where
A is the arc set of the directed graph D and by Theorem 4, finding a separator in
I′
takes O(n3
k4k
) time. Therefore the total time to solve the dag-bipartition
fvs problem is O(l!(|A| + n3
k4k
)) = O(l!n3
k4k
). ⊓⊔
Now, we introduce our FPT algorithm for the directed FVS problem.
Theorem 6. Given a directed graph D = (V, A) and an integer k, then in time
of O(n4
(1.48k)k
), we can either find an FVS F of size bounded by k in the graph
D, or report no such an F exists.
Proof. To solve the FVS problem in a directed graph D, we apply the iterative
compression technique. First, we use a greedy algorithm to find an FVS F′
. If
|F′
| ≤ k, then the problem is solved. Else in case of |F′
| > k, we remove |F′
| − k
vertices from F′
to obtain a new graph D′
; then the new graph D′
has an FVS
of size k. Second, step by step, we add the vertices, that have been removed from
the graph, back. In each step, we add one vertex back to D′
to obtain a new
graph D′′
, then the new graph D′′
= (V ′′
, A′′
) has an FVS of size k + 1. If we
can find an FVS of size bounded by k in D′′
, we continue to add another vertex
back and find an FVS of size bounded by k in the new graph, and so on. If we
can not find an FVS of size bounded by k in the graph D′′
in some step, we can
conclude that the graph D does not have an FVS F of size bounded by k. If we
add all vertices back and still find an FVS F of size bounded by k, then this F
is just the FVS we need.
In a directed graph D′′
that has an FVS F′′
of size k + 1, if D′′
has an
FVS F of size bounded by k, then there is a subset F1 such that F ∩ F′′
= F1
Directed Feedback Vertex Set Problem is FPT 15
and 0 ≤ |F1| = i ≤ k. It is obvious that both induced grpahs D′′
(V ′′
− F′′
)
and D′′
(F′′
− F1) are acyclic. We remove F1 form D′′
(we need to try at most
k+1
i possible cases, then we can make sure that in one case, F1 is removed
from D′′
). In the new graph D′′
− F1 = D′′′
= (V ′′′
, A′′′
), if we find an FVS
F2 ⊂ (V ′′′
−(F′′
−F1)) = (V ′′
−F′′
) of size bounded by j = k−i, then F1 ∪F2 is
an FVS of size bounded by k in the directed graph D′′
. In the new directed graph
D′′′
, as D′′′
(V ′′′
−(F′′
−F1)) = D′′
(V ′′
−F′′
) and D′′′
(F′′
−F1) = D′′
(F′′
−F1) are
acyclic, hence (D′′′
, V ′′′
−F′′
, F′′
−F1, j) is an instance of the dag-bipartition
fvs problem, where |F′′
− F1| = k + 1 − i = j + 1. By Theorem 5, this instance
can be solved in O((j + 1)!n3
j4j
) time.
From above proof, the total time complexity to solve the FVS problem in
directed graph is:
O(n
k
j=0
k + 1
i
(j + 1)!n3
j4j
) = O(n
k
j=0
k + 1
j + 1
(j + 1)!n3
j4j
)
= O(n4
k
j=0
(k + 1)!
(k − j − 1)!
j4j
)
≤ O(n4
(k + 1)!k
k
j=0
4j
)
≤ O(n4
(k + 1)!k4k+1
)
≤ O(n4
k2.5
(1.48k)k
)
This completes the proof of the theorem. ⊓⊔
Remark As there exists a polynomial time approximation algorithm of ratio
O(log τ∗
log log τ∗
) for the minimum feedback vertex set problem in directed
graph [11], where τ∗
is the size of the minimum feedback vertex set, we can
apply this approximation algorithm at first. If the size of FVS F′
we found by
the approximation algorithm is larger than O(k log k log log k), then we conclude
that the instance of the FVS problem has no FVS of size bounded by k. In case
of |F′
| ≤ O(k log k log log k), we only remove O(k log k log log k) vertices from F′
to make the new graph D′
have an FVS of size bounded by k. Hence, we need
to add at most O(k log k log log k) vertices (not O(n) vertices as before) back to
graph D′
. Therefore the algorithm to solve FVS problem in directed graph can
be improved to O(n3
k3.5
log k log log k(1.48k)k
).
As the feedback arc set problem in directed graph D has an FAS of size
bounded by k if and only if the feedback vertex set problem in D’s line
graph has an FVS of size bounded by k [11], therefore we can conclude that the
parameterized feedback arc set (FAS) problem can also be solved in time
of O(n3
k3.5
log k log log k(1.48k)k
).
Theorem 7. Given a directed graph D = (V, A) and an integer k, then in time
of O(n3
k3.5
log k log log k(1.48k)k
), we can either find an FAS F of size bounded
by k in the graph D, or report no such an F exists.
16 J. Chen, Y. Liu, S. Lu
6 Conclusion
In this paper, we solve a long standing open problem in FPT world: if the parameterized
FVS problem in directed graph is fixed-parameter tractable (FPT)?
Our answer is “Yes”, i.e. the parameterized FVS problem in directed graph
is fixed-parameter tractable. And we give an FPT algorithm of running time
O(n4
k2.5
(1.48k)k
) for the parameterized FVS problem in the directed graph.
This is a good news for the FVS problem in directed graph which means that
this problem can be solved efficiently when the size of FVS is not very large. We
can even design better algorithm for FVS problem in directed graph to solved
many practical problems in applications.
The parameterized FVS problem in directed graph is a very important problem
and our result is still in a very prime stage. The following are some FVS
problems in directed graph that are very interesting and worth of a further study.
(1) Given an instance I of the FVS problem in directed graph, can we reduce
the instance I into another instance I′
of the FVS problem in directed graph
in polynomial time, such that I is a “Yes” instance if and only if I′
is a “Yes”
instance, and input size of I′
is bounded by a function of k? (Kernelization) (2)
Is the FVS problem in directed graph has an FPT algorithm of running time
O(ck
nO(1)
), where c is a constant? (3) In directed graph that each vertex has a
weight of positive real number, let the weight of an FVS F be the weight sum
of vertices in F. If the graph has an FVS of size bounded by k, then is there an
FPT algorithm that find an FVS of size bounded by k with minimum weight?
References
1. V. Bafna, P. Berman, and T. Fujito. A 2-approximation algorithm for the undirected
feedback vertex set problem. SIAM J. Discrete Math., 12(1999), pp.289–297.
2. A. Becker, R. Bar-Yehuda, and D. Geiger. Randomized algorithms for the loop
cutset problem. J. Artificial Intelligence Res., 12(2000), pp.219–234.
3. H. Bodlaender. On disjoint cycles. Int. J. Found. Comput. Sci., 5(1994), pp.59–68.
4. G. Chartrand and L. Lesniak. Graphs & Digraphs. The Wadsworth & Brooks/Cole
Mathematics Series, (Second edition), 1986.
5. J. Chen, F. Fomin, Y. Liu, S. Lu, and Y. Villanger. Improved Algorithms for the
Feedback Vertex Set Problems. WADS (2007) to appear.
6. F. Dehne, M. Fellows, M. Langston, F. Rosamond, and K. Stevens. An
O(2O(k)n3) fpt algorithm for the undirected feedback vertex set problem. COCOON,
volume 3595 of Lecture Notes in Computer Science, (2005), pp.859–869.
7. M. Dom, J. Guo, F. uffner, R. Niedermeier, and A. Tru. Fixed-Parameter Tractability
Results for Feedback Set Problems in Tournaments. Proc. 6th CIAC-06, volume
3998 of Lecture Notes in Computer Science, (2006), pp.320–331.
8. R. Downey and M. Fellows. Fixed Parameter Tractability and Completeness. Complexity
Theory: Current Research, Cambridge University Press, (1992), pp.191–225.
9. R. Downey and M. Fellows. Parameterized Complexity. Springer-Verlag, New York,
1999.
10. R. Downey, M. Fellows. Fixed-Parameter Tractability and Completeness I: Basic
Results Theoretical Computer Science, (1995).
Directed Feedback Vertex Set Problem is FPT 17
11. G. Even, J. Naor, B. Schieber, and M. Sudan. Approximating minimum feedback
sets and multicuts in directed graphs. Algorithmica, 20(1998), pp.151-174.
12. H. Fernau. A top-down approach to search-trees: Improved algorithmics for 3hitting
set. Technical Report TR04-073, Electronic Colloquium on Computational
Complexity, 2004.
13. F. Fomin, S. Gaspers, and A. Pyatkin. Finding a minimum feedback vertex set
in time O(1.7548n
). IWPEC, volume 4169 of Lecture Notes in Computer Science,
(2006), pp.184–191.
14. G. Gardarin, and S. Spaccapietra. Integrity of Databases: A General Lockout
Algorithm with Deadlock Avoidance. In Modeling in Data Base Management
System, G. M. Nijsssen, ed., North-Holland, Amsterdam, (1976), pp.395–411.
15. M. Garey, D. Johnson. Computers and Intractability: A guide to the Theory of
NP-Completeness. W.H. Freeman, 1979.
16. J. Guo, J. Gramm, F. H¨uffner, R. Niedermeier, and S. Wernicke. Compressionbased
fixed-parameter algorithms for feedback vertex set and edge bipartization.
J. Comput. Syst. Sci., 72(2006), pp.1386–1396.
17. J. Guo, J. Gramm, F. Huffner, R. Niedermeier, and S. Wernicke. Improved fixedparameter
algorithms for two feeback set problems. WADS, volume 3608 of Lecture
Notes in Computer Science, (2004), pp.158–168.
18. G. Gutin, and A. Yeoy. Some Parameterized Problems on Digraphs, (Survey)
19. I. Kanj, M. Pelsmajer, and M. Schaefer. Parameterized algorithms for feedback
vertex set. IWPEC, volume 3162 of Lecture Notes in Computer Science, (2004),
pp.235–247.
20. R. Karp. Reducibility among combinatorial problems. in R. Miller and J.
Thatcher(eds.), Complexity of Computer Compuattions, Plenum Press, New York,
pp.85-103.
21. V. Raman, S. Saurabh, and C. Subramanian. Faster fixed parameter tractable
algorithms for undirected feedback vertex set. ISAAC 2002, volume 2518 of Lecture
Notes in Computer Science, (2002), pp.241–248.
22. V. Raman, S. Saurabh, and C. Subramanian. Faster fixed parameter tractable
algorithms for finding feedback vertex sets. ACM Trans. Algorithms, 2(2006),
pp.403–415.
23. V. Raman and S. Saurabh. Parameterized complexity of directed feedback set
problems in tournaments. WADS, volume 2748 of Lecture Notes in Computer
Science, (2003), pp.484–492.
24. V. Raman and S. Saurabh. Parameterized algorithms for feedback set problems and
their duals in tournaments. Theoretical Computer Science,, 351(2006), pp.446-458.
25. V. Raman, S. Saurabh, and C. Subramanian. Faster Fixed Parameter Tractable
Algorithms for Finding Feedback Vertex Sets. ACM Transactions on Algorithms,
(2006)2, pp.403-415.
26. I. Razgon. Exact computation of maximum induced forest. SWAT, volume 4059
of Lecture Notes in Computer Science, (2006), pp.160–171.
27. A. Silberschatz and P. Galvin. Operating System Concepts, 4th edition. In complexity
of Computer Computations, pp. 85-104, Plenum Press, N.Y., 1972.
28. E. Speckenmeyer. On feedback problems in digraphs. WG volume 411 of Lecture
Notes in Computer Science, (1989), pp.218–231.