Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference.
A feedback vertex set of an undirected graph is a subset of vertices that intersects with the vertex set of each cycle in the graph. Given an undirected graph G with n vertices and weights on its vertices, polynomial-time algorithms are provided for approximating the problem of finding a feedback vertex set of G with smallest weight. When the weights of all vertices in G are equal, the performance ratio attained by these algorithms is 4-(2/n). This improves a previous algorithm which achieved an approximation factor of $O(\sqrt{\log n})$ for this case. For general vertex weights, the performance ratio becomes $\min\{2\Delta^2, 4 \log_2 n\}$ where $\Delta$ denotes the maximum degree in G. For the special case of planar graphs this ratio is reduced to 10. An interesting special case of weighted graphs where a performance ratio of 4-(2/n) is achieved is the one where a prescribed subset of the vertices, so-called blackout vertices, is not allowed to participate in any feedback vertex set.It is shown how these algorithms can improve the search performance for constraint satisfaction problems. An application in the area of Bayesian inference of graphs with blackout vertices is also presented.
Introduction
E) be an undirected graph and let be a weight function on
the vertices of G. A cycle in G is a path whose two terminal vertices coincide. A feedback
vertex set of G is a subset of vertices F ' V (G) such that each cycle in G passes through
at least one vertex in F . In other words, a feedback vertex set F is a set of vertices of
G such that by removing F from G, along with all the edges incident with F , a forest is
obtained. A minimum feedback vertex set of a weighted graph (G; w) is a feedback vertex
set of G of minimum weight. The weight of a minimum feedback vertex set will be denoted
by -(G; w).
The weighted feedback vertex set (WFVS) problem is defined as finding a minimum
feedback vertex set of a given weighted graph (G; w). The special case where w is the
constant function 1 is called the unweighted feedback vertex set (UFVS) problem. Given a
graph G and an integer k, the problem of deciding whether -(G; 1) - k is known to be
NP-Complete [GJ79, pp. 191-192]. Hence, it is natural to look for efficient approximation
algorithms for the feedback vertex set problem, particularly in view of the recent applications
of such algorithms in artificial intelligence, as we show in the sequel.
Suppose A is an algorithm that finds a feedback vertex set FA for any given undirected
weighted graph (G; w). We denote the sum of weights of the vertices in FA by w(FA ).
The performance ratio of A for (G; w) is defined by RA (G;
-(G;
performance ratio r A (n; w) of A for w is the supremum of RA (G; w) over all graphs G with
vertices and for the same weight function w. When w is the constant function 1, we call
r A (n; 1) the unweighted performance ratio of A. Finally, the performance ratio r A (n) of A
is the supremum of r A (n; w) over all weight functions w defined over graphs with n vertices.
An approximation algorithm for the UFVS problem that achieves an unweighted performance
ratio of 2 log 2 n is essentially contained in a lemma due to Erd-os and P'osa [EP62].
This result was improved by Monien and Schulz [MS81], where they achieved a performance
ratio of O(
log n).
In Section 2, we provide an approximation algorithm for the UFVS problem that achieves
an unweighted performance ratio of at most 4 \Gamma (2=n). Our algorithm draws upon a theorem
by Simonovits [Si67] and our analysis uses a result by Voss [Vo68]. Actually, we consider
a generalization of the UFVS problem, where a prescribed subset of the vertices, called
blackout vertices, is not allowed to participate in any feedback vertex set. This problem
is a subcase of the WFVS problem wherein each allowed vertex has unit weight and each
blackout vertex has infinite weight. Our interest in graphs with blackout vertices is motivated
by the loop cutset problem and its application to the updating problem in Bayesian
inference which is explored in Section 4.
In Section 3, we present two algorithms for the WFVS problem. We first devise a primal-dual
algorithm which is based on formulating the WFVS problem as an instance of the set
cover problem. The algorithm has a performance ratio of 10 for weighted planar graphs
and 4 log 2 n for general weighted graphs. This ratio is achieved by extending the Erd-os-
P'osa Lemma to weighted graphs. The second algorithm presented in Section 3 achieves
a performance ratio of weighted graphs, where \Delta(G) is the maximum
degree of G. This result is interesting for low degree graphs.
A notable application of approximation algorithms for the UFVS problem in artificial
intelligence due to Dechter and Pearl is as follows [DP87, De90]. We are given a set of
its values from a finite domain D i . Also, for
every are given a constraint subset R i;j ' D i \Theta D j which defines the allowable pairs
of values that can be taken by the pair of variables Our task is to find an assignment
for all variables such that all the constraints R i;j are satisfied. With each instance of the
problem we can associate an undirected graph G whose vertex set is the set of variables,
and for each constraint R i;j which is strictly contained in D i \Theta D j (i.e., R i;j
there is an edge in G connecting x i and x j . The resulting graph G is called a constraint
network and it is said to represent a constraint satisfaction problem.
A common method for solving a constraint satisfaction problem is by backtracking,
that is, by repeatedly assigning values to the variables in a predetermined order and then
backtracking whenever reaching a dead end. This approach can be improved as follows.
First, find a feedback vertex set of the constraint network. Then, arrange the variables
so that variables in the feedback vertex set precede all other variables, and apply the
backtracking procedure. Once the values of the variables in the feedback vertex set are
determined by the backtracking procedure, the algorithm switches to a polynomial-time
procedure solve-tree that solves the constraint satisfaction problem in the remaining
forest. If solve-tree succeeds, a solution is found; otherwise, another backtracking phase
occurs.
The complexity of the above modified backtracking algorithm grows exponentially with
the size of the feedback vertex set: If a feedback vertex set contains k variables, each
having a domain of size 2, then the procedure solve-tree might be invoked up to 2 k
times. A procedure solve-tree that runs in polynomial-time was developed by Dechter
and Pearl, who also proved the optimality of their tree algorithm [DP88]. Consequently,
our approximation algorithm for finding a small feedback vertex set reduces the complexity
of solving constraint satisfaction problems through the modified backtracking algorithm.
Furthermore, if the domain size of the variables varies, then solve-tree is called a number
of times which is bounded from above by the product of the domain-sizes of the variables
whose corresponding vertices participate in the feedback vertex set. If we take the logarithm
of the domain size as the weight of a vertex, then solving the WFVS problem with these
weights optimizes the complexity of the modified backtracking algorithm in the case where
the domain size is allowed to vary.
2 The Unweighted Feedback Vertex Set Problem
The best approximation algorithm prior to this work for the UFVS problem attained a
performance ratio of O(
log n) [MS81]. We now use some results of [Si67] and [Vo68]
in order to obtain an approximation algorithm for the UFVS problem which attains a
performance In fact, we actually consider a slight generalization of the UFVS
problem where we mark each vertex of a graph as either an allowed vertex or a blackout
vertex. In such graphs, feedback vertex sets cannot contain any blackout vertices. We
denote the set of allowed vertices in G by A(G) and the set of blackout vertices by B(G).
Note that when problem reduces to the UFVS problem. A feedback vertex
set can be found in a graph G with blackout vertices if and only if every cycle in G contains
at least one allowed vertex. A graph G with this property will be called a valid graph. The
motivation for dealing with this modified problem is clarified in Section 4 where we use the
algorithm developed herein to reduce the computational complexity of Bayesian inference.
Throughout this section, G denotes a valid graph with a nonempty set of vertices V (G)
which is partitioned into a nonempty set A(G) of allowed vertices, a possibly empty set
B(G) of blackout vertices, and a set of edges E(G) possibly with parallel edges and self-
loops. We use - a (G) as a short-hand notation for -(G; w) where w assigns unit weight to
each allowed vertex and an infinite weight to each blackout vertex. A neighbor of v is a
vertex which is connected to v by an edge in E(G). The degree \Delta G (v) of v in G
is the number of edges that are incident with v in G. A self-loop at a vertex v contributes 2
to the degree of v. The degree of G, denoted \Delta(G), is the largest among all degrees of
vertices in G. A vertex in G of degree 1 is called an endpoint . A vertex of degree 2 is called
a linkpoint and a vertex of any higher degree is called a branchpoint. A graph G is called
rich if every vertex in V (G) is a branchpoint. The notation \Delta a (G) will stand for the largest
among all degrees of vertices in A(G) (a degree of a vertex in A(G) takes into account all
incident edges, including those that lead to neighbors in B(G)). In a rich valid graph we
have \Delta a (G) - 3.
Two cycles in a valid graph G are independent if their vertex sets share only blackout
vertices. Note that the size of any feedback vertex set of G is bounded from below by the
largest number of pairwise independent cycles that can be found in G. A cycle \Gamma in G is
called simple if it visits every vertex in V (G) at most once. Clearly, a set F is a feedback
vertex set of G if and only if it intersects with every simple cycle in G. A graph is called
a singleton if it contains only one vertex. A singleton is called self-looped if it contains at
least one self loop; for a singleton we have -(G; it is self-looped and -(G;
otherwise.
A graph G is connected if for every two vertices there is a connecting path in G. Every
graph G can be uniquely decomposed into isolated connected components
Similarly, every feedback vertex set F of G can be partitioned into feedback vertex sets
such that F i is a feedback vertex set of G i . Hence, - a
A 2-3-subgraph of a valid graph G is a subgraph H of G such that the degree in H of
every vertex in A(G) is either 2 or 3. The degree of a vertex belonging to B(G) in H is
not restricted. A 2-3-subgraph exists in any valid graph which is not a forest. A maximal
2-3-subgraph of G is a 2-3-subgraph of G which is not a subgraph of any other 2-3-subgraph
of G. A maximal 2-3-subgraph can be easily found by applying depth-first-search (DFS)
on G.
A linkpoint v in a 2-3-subgraph H is called a critical linkpoint if v is an allowed vertex,
and there is a cycle \Gamma in G such that fvg. We refer to such a cycle \Gamma
in G as a witness cycle of v. Note that we can assume a witness cycle to be simple and, so,
verifying whether a linkpoint v in H is a critical linkpoint is easy: Remove the set of vertices
G, with all incident edges, and apply a breadth-first-search (BFS)
to check whether there is a cycle through v in the remaining graph.
A cycle in a valid graph G is branchpoint-free if it does not pass through any allowed
branchpoints; that is, a branchpoint-free cycle passes only through allowed linkpoints and
blackout vertices of G.
The rest of this section is devoted to showing that the following algorithm correctly
outputs a vertex feedback set and achieves an unweighted performance ratio less than 4.
Algorithm SubG-2-3 (Input: valid graph G;
Output: feedback vertex set F of G);
if G is a forest then
F / ;;
else begin:
Using DFS, find a maximal 2-3-subgraph H of G;
Using BFS, find the set X of critical linkpoints in H;
Let Y be the set of allowed branchpoints in H;
Find a set W that covers all branchpoint-free cycles of H which
are not covered by X;
end.
Note that if are isolated cycles in H and so
W consists of one vertex of each such cycle.
We elaborate on how the set W is computed when B(G) 6= ;. Let H 0 be a graph obtained
from H by removing the set X along with its incident edges. Let H b be the subgraph of
induced by the allowed linkpoints and blackout vertices of H 0 . For every isolated cycle
in H b , we arbitrarily choose an allowed linkpoint from that cycle to W . Next, we replace
each maximal (with respect to containment) chain of allowed linkpoints in H b by an edge,
resulting in a graph H
b . We assign unit cost to all edges corresponding to a chain of allowed
linkpoints, and a zero cost to all other edges, and compute a minimum-cost spanning forest
T of H
b . We now add to W one linkpoint from each chain of allowed linkpoints in H b that
corresponds to an edge in H
It is now straightforward to verify that the complexity
of SubG-2-3 is linear in jE(G)j.
The following two lemmas, which generalize some claims used in the proof of Theorem 1
in [Si67], are used to prove that SubG-2-3 outputs a feedback vertex set of a valid graph
G.
H be a maximal 2-3-subgraph of a valid graph G and let \Gamma be a simple cycle
in G. Then, one of the following holds:
(a) \Gamma is a witness cycle of some critical linkpoint of H, or -
allowed branchpoint of H, or -
(c) \Gamma is a cycle in H that consists only of blackout vertices or allowed linkpoints of H.
Proof. Let \Gamma be a simple cycle in G and assume to the contrary that neither of (a)-(c)
holds. This implies in particular that \Gamma cannot be entirely contained in H. We distinguish
between two cases: (1) \Gamma does not intersect with H; and (2) \Gamma intersects with H only in
blackout vertices and allowed linkpoints of H.
Case 1: In this case we could join \Gamma and H to obtain a 2-3-subgraph H   of G that
contains H as a proper subgraph. This however contradicts the maximality of H.
Case 2: If \Gamma intersects with H only in blackout vertices, then as in case 1, we can join \Gamma
and H and contradict the maximality of H. Suppose now that \Gamma intersects with H in some
allowed linkpoints of H. Note that in such a case \Gamma must intersect with H in at least two
distinct allowed linkpoints of H, or else \Gamma would be a witness cycle of the only intersecting
(critical) linkpoint. Since \Gamma is not contained in H by assumption, we can find two allowed
linkpoints v 1 and v 2 in V (\Gamma) " V (H) that are connected by a path P along \Gamma such that
and P is not entirely contained in H. Joining P and H,
we obtain a 2-3-subgraph of G that contains H as a proper subgraph, thus contradicting
the maximality of H.
H be a maximal 2-3-subgraph of G and let \Gamma 1 and \Gamma 2 be witness cycles in
G of two distinct critical linkpoints in H. are independent cycles, namely,
Proof. Let v 1 and v 2 be the critical linkpoints associated with respectively,
and assume to the contrary that V contains an allowed vertex
Then, there is a path P in G that runs along parts of the cycles \Gamma 1 and \Gamma 2 , starting from
passing through u, and ending at v 2 . are witness cycles, we have
g. And, since v 1 and v 2 are distinct critical linkpoints, the
vertex u cannot possibly coincide with either of them. Therefore, the path P is not entirely
contained in H. Joining P and H we obtain a 2-3-subgraph of G that contains H as a
proper subgraph, thus reaching a contradiction.
Theorem 3 For every valid graph G, the set F computed by SubG-2-3 is a feedback vertex
set of G.
Proof. Let \Gamma be a simple cycle in G. We follow the three cases of Lemma 1 to show that
(a) \Gamma is a witness cycle of some critical linkpoint of H. By construction, all critical
linkpoints of H are in F .
allowed branchpoint of H. By construction, all allowed
branchpoints of H are in F .
(c) \Gamma is a cycle in H that consists only of blackout vertices or allowed linkpoints of
contains a critical linkpoint, then SubG-2-3 selects that linkpoint into
the feedback vertex set F . Otherwise, the cycle \Gamma must be entirely contained in the graph
H b that was used to create W . We now show that W covers all cycles in H b . Assume the
contrary and let \Gamma be a cycle in H b that is not covered by W . Recall that in the construction
of H
b , each chain of allowed linkpoints in \Gamma was replaced by an edge with a unit cost. Let
be the resulting cycle in H
b . Since W does not cover \Gamma, all unit-cost edges in \Gamma   were
necessarily chosen to the minimum-cost spanning forest T . On the other hand, since T
does not contain any cycles, there must be at least one zero-cost edge of \Gamma   which is not
contained in T . Hence, by deleting one of the unit-cost edges of \Gamma   from T and inserting
instead a particular zero-cost edge of \Gamma   into T , we can obtain a new spanning forest T 0 for
b . However, the cost of T 0 is smaller than that of T , which contradicts our assumption
that T is a minimum-cost spanning forest.
A reduction graph G 0 of an undirected graph G is a graph obtained from G by a sequence
of the following transformations:
ffl Delete an endpoint and its incident edge.
ffl Connect two neighbors of a linkpoint v (other than a self-looped singleton) by a new
edge and remove v from the graph with its two incident edges.
A reduction graph of a valid graph G is not necessarily valid, since the reduction process
may generate a cycle consisting of blackout vertices only. We will be interested in reduction
sequences in which each transformation yields a valid graph.
Lemma 4 Let G 0 be a reduction graph of G. If G 0 is valid, then - a
Proof. Let G; be a sequence of reduction graphs where each
H i is obtained by a removal of one linkpoint and possibly some endpoints from H i\Gamma1 . Since
G 0 is valid, each H i is a valid graph as well. Let v i be the linkpoint that is removed from
H i to obtain H i+1 .
First we show that - a (G 0 ) - a (G). Suppose F is a feedback vertex set of H i+1 for some
be a cycle in H i that passes through v i . A reduction of \Gamma obtained
by replacing the linkpoint v i on \Gamma by an edge connecting the neighbors of v i yields a cycle
in H i+1 . The vertex set of - \Gamma intersects the set F . Hence, F is also a feedback vertex set
of H i which implies that - a (H
Now we show that - a (G 0 ) - a (G). Suppose F is a minimal feedback vertex set of H i .
If F does not contain v i , then F is also a feedback vertex set of H i+1 . Otherwise, write
We claim that the set F 0 cannot fail to cover more than one cycle in H i+1 .
If it failed, then there would be two distinct cycles \Gamma 1 and \Gamma 2 in H i that contain v i , in
which case the cycle in H i induced by (V would not be covered by F ,
thus contradicting the fact that F is a feedback vertex set of H i . It follows by this and the
minimality of F that the set F 0 fails to cover exactly one cycle in H i+1 . This cycle contains
at least one allowed vertex u because H i+1 is a valid graph. Therefore, the set F 0 [ fug is
a feedback vertex set of H i+1 . Hence, - a (H
A reduction graph G   of a graph G is minimal if and only if G   is a valid graph and
any proper reduction graph G 0 of G   is not valid.
Lemma 5 If G   is a minimal reduction graph of G, then G   does not contain blackout
linkpoints, and every feedback vertex set of G   contains all allowed linkpoints of G   .
Proof. Recall that G   is a valid graph. If G   contains a blackout linkpoint, then its removal
creates a valid reduction graph which contradicts the minimality of G   . Now assume F is
a feedback vertex set of G   and v is an allowed linkpoint which is not in F . If the removal
of v yields a graph that is not valid, then v must have been included in F . If the removal
of v yields a valid graph, then G   is not minimal.
The next lemma is needed in order to establish the performance ratio of SubG-2-3. It
is a variant of Lemma 4 in [Vo68].
Lemma 6 Let G be a valid graph with no blackout linkpoints and such that no vertex has
degree less than 2. Then, for every feedback vertex set F of G which contains all linkpoints
of G,
Proof.
Suppose (G). In this case we have jV (G)j - 3jV
and, therefore, the lemma holds trivially. So we assume from now on that jF j ! jV (G)j.
denote the set of edges in E(G) whose terminal vertices are all vertices in F .
denote the set of edges in E(G) whose terminal vertices are
all vertices in X. Also, let E F;X denote the set of those edges in G that connect vertices in
F with vertices in X. Clearly, E F , EX , and E F;X form a partition on E(G). Now, the graph
obtained by deleting F from G is a nonempty forest on X and, therefore, jE
However, each vertex in X is a branchpoint in G because all linkpoints are assumed to be
in F and there are no vertices of degree less than 2. Therefore,
i.e.,
On the other hand,
Combining the last two inequalities we obtain
The main claim of this section now follows.
Theorem 7 The unweighted performance ratio of SubG-2-3 is at most 4 \Gamma (2=jV (G)j).
Proof. Let F be the feedback vertex set computed by SubG-2-3 for a valid graph G which
is not a forest. We show that jF j - 4 - a 2. The theorem follows immediately from
this inequality.
Let H, X, Y , and W be as in SubG-2-3. Suppose - a cycles in G
pass through some allowed vertex v in G and, so, no vertex other than v can be a critical
linkpoint in H. Now, if v is a linkpoint in H, then H is a cycle. Otherwise, one can readily
verify that H must contain exactly two branchpoints. In either case we have jF j - 2. We
assume from now on that - a (G) - 2.
For every v i 2 X, let \Gamma i be some witness cycle of v i in G. By Lemma 2, the cycles \Gamma i
are pairwise independent. Therefore, the minimum number of vertices needed to cover such
cycles is jXj.
Let f\Gamma
j g be the set of branchpoint-free cycles in H that do not contain any critical
linkpoints of H. Note that each cycle \Gamma
j is independent with any witness cycle \Gamma i . We
now claim that any smallest set W 0 of vertices of V (H) that intersects with the vertex set
of each \Gamma
j must be of size jW j. To see this, note that W 0 contains only allowed linkpoints
of H. If we remove from H
b all the edges that correspond to linkpoints belonging to W 0 ,
then we clearly end up with a forest. By construction, the minimum number of edges (or
allowed linkpoints), needed to be removed from H
b so as to make it into a forest, is jW j.
Recalling that every cycle \Gamma
j is independent with any witness cycle \Gamma i , the set W 0 cannot
possibly intersect with any of the cycles \Gamma i . Hence, in order to cover the cycles f\Gamma
in G, we will need at least jXj vertices. Therefore,
On the other hand, we recall that jF
We distinguish between the following two cases.
Case 1: Here we have,
Case 2:  be a feedback vertex set of G of size - a (G) and let
W 0 be a smallest subset of F   that intersects with the vertex set of each \Gamma
. Clearly, W 0
consists of allowed linkpoints of H, and, as we showed earlier in this proof, jW
H 1 be the subgraph of H obtained by removing all critical linkpoints of H and all linkpoints
in W 0 . With each deleted linkpoint, we also remove recursively all resulting endpoints from
H while obtaining H 1 . Thus, a deletion of a linkpoint from H can decrease the number
of branchpoints by 2 at most. Hence, the number of branchpoints left in H 1 is at least
Furthermore, the graph H 1 does not contain any endpoints.
1 be a minimal reduction graph of H 1 and let H 2 be a valid graph obtained by
removing all singleton components from H
1 . Since H 1 does not contain any endpoints,
the number of branchpoints of H 1 is preserved in H
1 and in H 2 . Therefore, the graph H 2
contains at least jY branchpoints. On the other hand, since H
1 is a minimal
reduction and due to Lemma 5, there are no blackout linkpoints in H
1 and every feedback
vertex set of H
1 contains all allowed linkpoints of H
1 . Furthermore, the graphs H
do not contain any endpoints.
It follows that we can apply Lemma 6 to H 2 and any feedback vertex set of H 2 , thus
obtaining
where the equality is due to Lemma 4. Therefore,
Recall that W 0 was chosen as a subset of a smallest feedback vertex set F   of G. Let
X 0 be a smallest subset of F   that covers the witness cycles f\Gamma i g and let Z 0 be a smallest
subset of F   that covers the cycles of H 1 . Since H 1 does not contain any of the critical
linkpoints of H, each witness cycle \Gamma i is independent with any cycle in H 1 and, so, we have
It also follows from our previous discussion that In addition, by
construction of H 1 we have It thus follows that
Combining with (1), we obtain the desired result.
Weighted Feedback Vertex Set
In this section, we consider the approximation of the WFVS problem described in Section 1.
That is, given an undirected graph G and a weight function w on its vertices, find a feedback
vertex set of (G; w) with minimum weight. As in the previous section, we assume that G
may contain parallel edges and self-loops.
A weighted reduction graph G 0 of an undirected graph G is a graph obtained from G by
a sequence of the following transformations:
ffl Delete an endpoint and its incident edge.
ffl Let u and v be two adjacent vertices such that w(u) - w(v) and v is a linkpoint.
Connect u to the other neighbor of v, and remove v from the graph with its two
incident edges.
The following lemma can be easily verified. (See, e.g., the proof of Lemma 4).
weighted reduction graph of (G; w). Then, -(G
A weighted reduction graph G   of a graph G is minimal if and only if any weighted
reduction graph G 0 of G   is equal to G   . A graph is called branchy if it has no endpoints
and, in addition, its set of linkpoints induces an independent set, i.e., each linkpoint is either
an isolated self-looped singleton or connected to two branchpoints. Clearly, any minimal
weighted reduction graph must be branchy. We note that the complexity of transforming a
graph into a branchy graph is linear in jE(G)j.
We are now ready to present our algorithms for finding an approximation for a minimum-weight
feedback vertex set of a given weighted graph. In Section 3.1 we give an algorithm
that achieves a performance ratio of 4 log 2 jV (G)j. In Section 3.2 we present an algorithm
that achieves a performance ratio of
3.1 The primal-dual algorithm
The basis of the first approximation algorithm is the next lemma which generalizes a lemma
due to Erd-os and P'osa [EP62, Lemma 3]. That lemma was obtained by Erd-os and P'osa
while estimating the smallest number of edges in a graph which contains a given number
of pairwise independent cycles. Later on, in [EP64], they provided bounds on the value of
-(G; 1) in terms of the largest number of pairwise independent cycles in G. Tighter bounds
on -(G; 1) were obtained by Simonovits [Si67] and Voss [Vo68].
Lemma 9 The shortest cycle in any branchy graph G with at least two vertices is of length
Proof. Let t be the smallest even integer such that 2 \Delta 2 t=2 ? jV (G)j. Apply BFS on G
of depth t starting at some vertex v. We now claim that the search hits some vertex twice
and so there exists a cycle of length - 2t in G. Indeed, if it were not so, then the induced
BFS tree would contain at least 2 \Delta 2 t=2 distinct vertices of G, which is a contradiction.
In each iteration of the proposed algorithm, we first find a minimal weighted reduction
graph, and then find a cycle \Gamma with the smallest number of vertices in the minimal weighted
reduction graph. The algorithm sets ffi to be the minimum among the weights of the vertices
in V (\Gamma). This value of ffi is subtracted, in turn, from the weight of each vertex in V (\Gamma).
Vertices whose weight becomes zero are added to the feedback vertex set and deleted from
the graph. Each such iteration is repeated until the graph is exhausted.
Algorithm MiniWCycle (Input: (G; w); Output: feedback vertex set F of (G; w));
While H is not a forest do begin:
Find a minimal weighted reduction graph
Find a cycle \Gamma 0 in H 0 with the smallest number of vertices;
Remove X (with all incident edges) from H
end.
Finding a shortest cycle can be done by running BFS from each vertex until a cycle is
found and then selecting the smallest. A more efficient approach for finding the shortest
cycle is described in [IR78].
It is not hard to see that MiniWCycle computes a feedback vertex set of G. We
now analyze the algorithm employing techniques similar to those used in [Ho82], [Ho83],
and [KhVY94]. We note that the algorithm can also be analyzed using the Local Ratio
Theorem of Bar-Yehuda and Even [BaEv85].
Theorem 10 The performance ratio of algorithm MiniWCycle is at most 4 log 2 jV (G)j.
Proof. We assume that jV (G)j ? 1. Given a feedback vertex set F of (G; w), let
be the indicator vector of F , namely, x
We denote by C the set of cycles in G. The problem of finding a minimum-weight feedback
vertex set of (G; w) can be formulated in terms of x by an integer programming problem
as follows:
minimize
ranging over all nonnegative integer vectors
(2)
Let C v denote the set of cycles passing through vertex v in G and consider the following
integer programming packing problem:
maximize
ranging over all nonnegative integer vectors \Gamma2C such that
Clearly, the linear relaxation of (3) is the dual of the linear relaxation of (2), with
being the dual variables.
weighted reduction graph computed at some iteration of
algorithm MiniWCycle. Then, for each cycle
as follows: If all vertices in V (\Gamma 0 ) belong to G, then Otherwise, we "unfold" the
transformation steps performed in obtaining H 0 from H in backward order, i.e., from H 0
back to H: In each such step we add to \Gamma 0 chains of linkpoints (connecting vertices in
that were deleted. When this process finishes, the cycle \Gamma 0 of H 0 transforms into a cycle \Gamma
of G.
We now show that MiniWCycle can be interpreted as a primal-dual algorithm. We
first show that it computes a dual feasible solution for (3) with a certain maximality prop-
erty. The initial dual feasible solution is the one in which all the dual variables y \Gamma are
zero.
i be a cycle chosen at iteration i of MiniWCycle and let \Gamma i be the associated
cycle in G. We may view the computation of iteration i of MiniWCycle as setting the
value of the dual variable y \Gamma i to the weight ffi of a lightest vertex in V (\Gamma 0
). The updated
weight wH 0 (v) of every
precisely the slack of the dual constraint
that corresponds to v.
It is clear that by the choice of ffi, the values of the dual variables y \Gamma at the end of
iteration i of MiniWCycle satisfy the dual constraints (4) corresponding to vertices
i ). It thus follows that the dual constraints hold for all vertices
Let v be a vertex that was removed from H to obtain H 0 in iteration i of MiniWCycle.
It remains to show that the dual constraint (4) corresponding to such a vertex holds in each
iteration j of the algorithm for every j - i.
We show this by backward induction on j. By the previous discussion it follows that
the constraints corresponding to vertices that exist in the last iteration all hold. Suppose
now that the dual constraints corresponding to vertices in V (H 0 ) in iteration j are not
violated. We show that the dual constraints corresponding to vertices in V
in that iteration are also not violated. Let c be a chain of linkpoints in H in iteration j,
and let v 1 and v 2 be the two branchpoints adjacent to c. Let u be a vertex of minimum
weight among v 1 , v 2 , and the vertices in c. We note that the weighted reduction procedure
deletes all vertices in c except possibly for one representative, depending on whether u is
in c or is one of its adjacent branchpoints. We now observe that the set of cycles that pass
through a linkpoint in c is the same for all linkpoints in c, and is contained in the set of
cycles that pass through v 1 , and is also contained in the set of cycles that pass through v 2 .
This implies that if the dual constraint corresponding to u is not violated, then the dual
constraints corresponding to any vertex in c is also not violated.
The algorithm essentially constructs a primal solution x from the dual solution y: It selects
into the feedback vertex set all vertices for which: (i) the corresponding dual constraints
are tight; and (ii) in the iteration the constraint first became tight, the corresponding vertex
belonged to the graph. As stated earlier, this construction yields a feasible solution.
Let x
denote the optimal primal and dual fractional
solutions, respectively. It follows from the duality Theorem that
w(v)
w(v)
\Gamma2C
y
\Gamma2C
Hence, to prove the theorem, it suffices to bound the ratio between the LHS and the RHS
of (5). First note that y \Gamma 6= 0 only for cycles \Gamma in G that are associated with cycles \Gamma 0
that were chosen at some iteration of MiniWCycle. By the above construction of x, it is
clear that the dual variable y \Gamma of each such cycle \Gamma contributes its value to at most V
vertices. Hence,
\Gamma2C
Now, in each iteration, the graph H 0 is a branchy graph. Therefore, by Lemma 9, we have
that jV (\Gamma 0 )j - 4 log 2 jV (G)j. Hence the theorem is proved.
Proposition 11 For planar graphs, the weighted performance ratio of MiniWCycle is at
most 10.
Proof. We first notice that the weighted reduction process preserves planarity and, there-
fore, at each iteration of algorithm MiniWCycle we remain with a planar graph.
We claim that every rich planar graph G must contain a face of length at most 5. Assume
the contrary. By summing up the lengths of all the faces, we get that 2jEj - 6jZj, where Z
denotes the set of faces of G. By Euler's formula,
Hence, However, since the degree of each vertex is at least 3, we get that
which is a contradiction. Furthermore, this implies that a branchy planar
graph must contain a cycle of length at most 10.
3.2 Low-degree graphs
The algorithm presented in this section is based on the following variant of Lemma 6.
Lemma 12 Let G be a branchy graph. Then, for every feedback vertex set F of G,
Proof. Let F be a feedback vertex set of G. We can assume without loss of generality that
F contains only branchpoints, since this assumption can only decrease jF j. Let G 0 be the
minimal (unweighted) reduction graph of G, i.e., G 0 contains only branchpoints or isolated
self-looped singletons. Clearly, F is also a feedback vertex set of G 0 . Thus, G 0 and F satisfy
the conditions of Lemma 6 (\Delta a = \Delta), yielding that,
Since G 0 is a branchy graph, the number of linkpoints in G can be at most \Delta(G 0 )
Hence,
We now present a weighted greedy algorithm for finding a feedback vertex set in a graph
G.
Algorithm WGreedy (Input: (G; w); Output: feedback vertex set F of (G; w));
while H is not a forest do begin:
Find a minimal weighted reduction graph (H 0
of (H; wH );
F
remove U i from H 0
i with its incident edges;
end.
For a subset S ' V , let w(S) denote the sum of weights of the vertices in S. We now
prove the following theorem.
Theorem 13 Let G be a branchy graph. Denote by F the feedback vertex set computed
by algorithm WGreedy, and by F   a minimum-weight feedback vertex set in G. Then,
Proof. Assume that the number of iterations the while loop is executed in algorithm
WGreedy is p. We define the following weight functions w (G). The weight
function w i is defined, for 1 - i - p, as follows:
For all
For a subset S, let w i (S) denote the sum of weights of the vertices in S, where the
weight function is w i . Clearly,
Suppose that at one of the weighted reduction steps of algorithm WGreedy, a chain c of
equal weight linkpoints was reduced to a single vertex, say, v, which either belongs to c or
is one of the two branchpoints adjacent to c. Suppose further that v was added to F . If F
also contains a vertex from the chain c, then without loss of generality, we can assume that
this vertex can be replaced by v.
Let Obviously,
1 . We claim that if
p. Assume this is not the case. Then, with respect to the order in which vertices
entered F in algorithm WGreedy, let u be the first vertex such that u 2 F ,
was removed from the graph in a weighted reduction step. This means that u was at the
time of its removal a linkpoint that had an adjacent vertex u 0 with smaller weight. But then,
by exchanging u for u 0 in F   , we obtain a feedback vertex set which has smaller weight,
contradicting the optimality of F   . Hence, for a vertex
Therefore,
Notice that in the graph H 0
i , the weight function w i assigns the same weight to all vertices.
Hence, by Lemma 12, we have that w i
the theorem follows.
It follows from Lemma 8 that the performance ratio of algorithm WGreedy for (G; w)
is at most 2\Delta 2 (G) for any graph G.
4 The Loop Cutset Problem and its Application
In section 4.1 we consider a variant of the WFVS problem for directed graphs and in
section 4.2 we describe its application to Bayesian inference.
4.1 The loop cutset problem
The underlying graph of a directed graph D is the undirected graph formed by ignoring
the directions of the edges in D. A loop in D is a subgraph of D whose underlying graph
is a cycle. A vertex v is a sink with respect to a loop \Gamma if the two edges adjacent to v in
are directed into v. Every loop must contain at least one vertex that is not a sink with
respect to that loop. Each vertex that is not a sink with respect to a loop \Gamma is called an
allowed vertex with respect to \Gamma. A loop cutset of a directed graph D is a set of vertices
that contains at least one allowed vertex with respect to each loop in D. Our problem is
to find a minimum-weight loop cutset of a given directed graph D and a weight function
We denote by -(D; w) the sum of weights of the vertices in such a loop cutset. Greedy
approaches to the loop cutset problem have been suggested by [SuC90] and [St90]. Both
methods can be shown to have a performance ratio as bad as \Omega\Gamma n=4) in certain planar
graphs [St90]. An application of our approximation algorithms to the loop cutset problem
in the area of Bayesian inference is described later in this section.
The approach we take is to reduce the weighted loop cutset problem to the weighted
feedback vertex set problem solved in the previous section. Given a weighted directed graph
(D; w), we define the splitting weighted undirected graph (D s ; w s ) as follows. Split each
vertex v in D into two vertices v in
and v out
in D s such that all incoming edges to v become
undirected incident edges with v in
, and all outgoing edges from v become undirected incident
edges with v out
. In addition, we connect v in
and v out
by an undirected edge. Set w s (v in
and w s (v out
w(v). For a set of vertices X in D s , we define /(X) as the set obtained
by replacing each vertex v in
or v out
in X by the respective vertex v in D from which these
vertices originated.
Our algorithm can now be easily stated.
Algorithm LoopCutset (Input: (D; w); Output: loop cutset F of (D; w));
Construct (D s
Apply MiniWCycle on (D s ; w s ) to obtain a feedback vertex set X;
F / /(X).
Note that each loop in D is associated with a unique cycle in D s , and vice-versa, in a
straightforward manner. Let I (\Gamma) denote the loop image of a cycle \Gamma in D s , and I -1 (K)
denote the cycle image of a loop K in D. It is clear that the mapping I is
The next lemma shows that algorithm LoopCutset outputs a loop cutset of (D; w).
Lemma 14 Let (D; w) be a directed weighted graph and (D s ; w s ) be its splitting graph.
Then: (i) If F is a feedback vertex set of (D s ; w s ) having finite weight, then /(F ) is a loop
cutset of (D; w), and w s U is a loop cutset of D, then the set U s
obtained from U by replacing each vertex v 2 U by vertex v out
s is a feedback vertex set
of D s , and
Proof. We prove (i). The proof of (ii) is similar. Let \Gamma be a loop in D. To prove the lemma
we show that an allowed vertex with respect to \Gamma belongs to /(F ). Let I -1 (\Gamma) be the unique
cycle image of \Gamma in D s . Since F is a cycle cover of D s having finite weight, there must be
a vertex v out
2 F in I -1 (\Gamma). Now, it is clear that vertex v 2 \Gamma from which v out
originated is
an allowed vertex with respect to \Gamma as needed. To complete the proof, by the finiteness of
must have w s for each vertex in F .
It follows from Lemma 14 that -(D; In addition, due to Theorem 10 applied
to the graph D s , and since the number of vertices in D s is twice the number of vertices
in D, we get the following bound on the performance ratio of algorithm LoopCutset.
Theorem 15 The performance ratio of LoopCutset is at most 4 log 2 (2jV (D)j).
We now show that in the unweighted loop cutset problem, we can achieve a performance
ratio better than 4. In this case, for each vertex v 2 D, the weight of v in 2 D s is one unit, and
the weight of v out 2 D s is 1. This falls within the framework considered in Section 2, since
vertices with infinite weight in D s can be treated as blackout vertices. We can therefore
apply SubG-2-3 in the LoopCutset algorithm instead of applying MiniWCycle and
obtain the following improved performance ratio.
Theorem using SubG-2-3, the unweighted performance ratio of LoopCutset
is at most 4 \Gamma (2=jV (D)j).
Proof. We have,
where the equality is due to Lemma 14, and the inequality is due to Theorem 7. Since
(D)j, the claim is proved.
4.2 An application
We conclude this section with an application of approximation algorithms for the loop cutset
problem.
Let P distribution where each u i draws values from a finite
set called the domain of u i . A directed graph D with no directed cycles is called a Bayesian
network of P if there is a 1-1 mapping between fu and vertices in D, such that
associated with vertex i and P can be written as follows:
Y
are the source vertices of the incoming edges to vertex i in D.
It is worth noting that Bayesian networks are useful knowledge representation schemes
for many artificial intelligence tasks. Bayesian networks allow a wide spectrum of independence
assumptions to be considered by a model builder so that a practical balance can
be established between computational needs and adequacy of conclusions. For a complete
exploration of this subject see [Pe88].
Suppose now that some variables fv among fu are assigned specific
values respectively. The updating problem is to compute the probability
In principle, such computations are
straightforward because each Bayesian network defines the joint probability distribution
conditional probabilities can be computed by dividing the appropriate
sums. However, such computations are inefficient both in time and space unless
they use conditional independence assumptions defined by Eq. (6). We shall see next how
our approximation algorithms for the loop cutset problem reduce the computations needed
for solving the updating problem.
A trail in a Bayesian network is a subgraph whose underlying graph is a simple path. A
vertex b is called a sink with respect to a trail t if there exist two consecutive edges a ! b
and b / c on t. A trail t is active by a set of vertices Z if (1) every sink with respect to
t either is in Z or has a descendant in Z and (2) every other vertex along t is outside Z.
Otherwise, the trail is said to be blocked by Z.
Verma and Pearl [VePe88] have proved that if D is a Bayesian network of P
and all trails between a vertex in fr and a vertex in fs are blocked by
g, then the corresponding sets of variables fu r 1
are
independent conditioned on fu t 1
g. Furthermore, Geiger and Pearl [GP90] proved
a converse to this theorem. Both results are presented and extended in [GVP90].
Using the close relationship between blocked trails and conditional independence, Kim
and Pearl [KiP83] developed an algorithm update-tree that solves the updating problem
on Bayesian networks in which every two vertices are connected with at most one trail.
update-tree views each vertex as a processor that repeatedly sends messages to each of
its neighboring vertices. When equilibrium is reached, each vertex i contains the conditional
probability distribution P computations reach equilibrium
regardless of the order of execution in time proportional to the length of the longest trail
in the network.
Pearl [Pe86] solved the updating problem on any Bayesian network as follows. First, a
set of vertices S is selected, such that any two vertices in the network are connected by at
most one active trail in S [ Z, where Z is any subset of vertices. Then, update-tree is
applied once for each combination of value assignments to the variables corresponding to S,
and, finally, the results are combined. This algorithm is called the method of conditioning
and its complexity grows exponentially with the size of S. Note that according to the
definition of active trails, the set S in Pearl's algorithm is a loop cutset of the Bayesian
network. In this paper we have developed approximation algorithms for finding S.
When the domain size of the variables varies, then update-tree is called a number
of times which is bounded from above by the product of the domain sizes of the variables
whose corresponding vertices participate in the loop cutset. If we take the logarithm of the
domain size as the weight of a vertex, then solving the weighted loop cutset problem with
these weights optimizes Pearl's updating algorithm in the case where the domain sizes are
allowed to vary.
It is useful to relate the feedback vertex set problem with the vertex cover problem in order
to establish lower bounds on the performance ratios attainable for the feedback vertex set
problem. A vertex cover of an undirected graph is a subset of the vertex set that intersects
with each edge in the graph. The vertex cover problem is to find a minimum weight vertex
cover of a given graph. There is a simple polynomial reduction from the vertex cover
problem to the feedback vertex set problem: Given a graph G, we extend G to a graph
H by adding a vertex v e for each edge e 2 E(G), and connecting v e with the vertices in
G with which e is incident in G. It is easy to verify that there always exists a minimum
feedback vertex set in H whose vertices are all in V (G) and this feedback vertex set is also
a minimum vertex cover of G. In essence, this reduction replaces each edge in G with a
cycle in H, thus transforming any vertex cover of G to a feedback vertex set of H.
Due to this reduction, it follows that the performance ratio obtainable for the feedback
vertex set problem cannot be better than the one obtainable for the vertex cover problem.
The latter problem has attracted a lot of attention over the years but has so far resisted any
approximation algorithm that achieves in general graphs a constant performance ratio less
than 2. We note that the above reduction retains planarity. However, for planar graphs,
Baker [Bak94] provided a Polynomial Approximation Scheme (PAS) for the vertex cover
problem. For the UFVS problem, there are examples showing that 4 is the tightest constant
performance ratio of algorithm SubG-2-3.
Another consequence of the above reduction is a lower bound on the unweighted performance
ratio of the following greedy algorithm, GreedyCyc, for the feedback vertex
set problem. In each iteration, GreedyCyc removes a vertex of maximal degree from
the graph, adds it to the feedback vertex set, and removes all endpoints in the graph. A
similar greedy algorithm for the vertex cover problem is presented in [Jo74] and in [Lo75].
The latter algorithm was shown to have an unweighted performance ratio no better than
\Omega\Gammahan jV (G)j) [Jo74]. Due to the reduction to the cycle cover problem, the same lower
bound holds also for GreedyCyc, as demonstrated by the graphs of [Jo74]. A tight upper
bound on the worst-case performance ratio of GreedyCyc is unknown.
Finally, one should notice that the following heuristics may improve the performance
ratios of our algorithms. For example, in each iteration MiniWCycle chooses to place
in the cover all zero-weight vertices found on the smallest cycle. This choice might be
rather poor especially if many weights are equal. It may be useful in this case to perturb
the weights of the vertices before running the algorithm. Similarly, in algorithm SubG-
2-3, there is no point in taking blindly all branchpoints of H. An appropriate heuristic
here may be to pick the branchpoints one by one in decreasing order of residual degrees.
Furthermore, the subgraph H itself should be constructed such that it contains as many
high degree vertices as possible.
Remark
In a preliminary version of this paper, presented in [BaGNR94], we conjectured that a
constant performance ratio is attainable by a polynomial time algorithm for the WFVS
problem. This has been recently verified in [BeG94, BaBF94] where a performance ratio of
2 has been obtained.

Acknowledgment

We would like to thank David Johnson for bringing [EP62] to our attention, and Samir
Khuller for helpful discussions.



--R

Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
Approximation algorithms for NP-complete problems on planar graphs
A local-ratio theorem for approximating the weighted vertex cover problem
Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
Approximation algorithms for the loop cutset prob- lem
The cycle cutset method for improving search performance in AI

Enhancement schemes for constraint processing: backjumping
On the maximal number of disjoint circuits of a graph
On the independent circuits contained in a graph

On the logic of causal models
independence in Bayesian networks
Approximation algorithms for set covering and vertex covering problems
Efficient bounds for the stable set
Finding a minimum circuit in a graph
Approximation algorithms for combinatorial problems
A primal-dual parallel approximation technique applied to weighted set and vertex cover
A computational model for combined causal and diagnostic reasoning in inference systems
On the ratio of optimal integral and fractional covers
Four approximation algorithms for the feedback vertex set problem

Probabilistic reasoning in intelligent systems: Networks of plausible infer- ence
A new proof and generalizations of a theorem by Erd-os and P'osa on graphs without k
On heuristics for finding loop cutsets in multiply connected belief networks
Cooper G.
Semantics and expressiveness
Some properties of graphs containing k independent circuits
--TR

--CTR
Paola Festa , Panos M. Pardalos , Mauricio G. C. Resende, Algorithm 815: FORTRAN subroutines for computing approximate solutions of feedback set problems using GRASP, ACM Transactions on Mathematical Software (TOMS), v.27 n.4, p.456-464, December 2001
Rudolf Berghammer , Alexander Fronk, Exact computation of minimum feedback vertex sets with relational algebra, Fundamenta Informaticae, v.70 n.4, p.301-316, April 2006
Rudolf Berghammer , Alexander Fronk, Exact Computation of Minimum Feedback Vertex Sets with Relational Algebra, Fundamenta Informaticae, v.70 n.4, p.301-316, December 2006
Ioannis Caragiannis , Christos Kaklamanis , Panagiotis Kanellopoulos, New bounds on the size of the minimum feedback vertex set in meshes and butterflies, Information Processing Letters, v.83 n.5, p.275-280, 15 September 2002
Maw-Shang Chang , Chin-Hua Lin , Chuan-Min Lee, New upper bounds on feedback vertex numbers in butterflies, Information Processing Letters, v.90 n.6, p.279-285,
Camil Demetrescu , Irene Finocchi, Combinatorial algorithms for feedback problems in directed graphs, Information Processing Letters, v.86 n.3, p.129-136, 16 May
Rastislav Krlovi , Peter Ruika, Minimum feedback vertex sets in shuffle-based interconnection networks, Information Processing Letters, v.86 n.4, p.191-196, 31 May
Jiong Guo , Jens Gramm , Falk Hffner , Rolf Niedermeier , Sebastian Wernicke, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Journal of Computer and System Sciences, v.72 n.8, p.1386-1396, December, 2006
Venkatesh Raman , Saket Saurabh , C. R. Subramanian, Faster fixed parameter tractable algorithms for finding feedback vertex sets, ACM Transactions on Algorithms (TALG), v.2 n.3, p.403-415, July 2006
Reuven Bar-Yehuda , Keren Bendel , Ari Freund , Dror Rawitz, Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004, ACM Computing Surveys (CSUR), v.36 n.4, p.422-463, December 2004
bayesian networks;combinatorial optimization;approximation algorithms;constraint satisfaction;vertex feedback set