Under Construction

(FVS) MINIMUM FEEDBACK VERTEX SET
Instance: Graph G=(V,E), for each vertex v in V a weight W(v)>=0;
Solution: An FVS cover for G, i.e., a subset C of V such that,
          (V-C,E) is cycle free (forest)
Measure : W(C) (i.e. Sum {W(v): v in C})

+-----------------------------------------------------------------+
|   The "Local-Ratio Theorem" (oriented for FVS)                  |
+-----------------------------------------------------------------+
|   If   C is 2-approximation FVS w.r.t the weight function W1    |
|   and  C is 2-approximation FVS w.r.t the weight function W2    |
|   then C is 2-approximation FVS w.r.t the weight function W1+W2 |
+-----------------------------------------------------------------+

Our objective is to find a MINIMAL-FVS C, i.e.
C is an FVS, but for each v in C: C-{v} is not FVS.

We can assume that G is LEAF-FREE, i.e.
for each vertex v: W(v)>0 and degree(v)>1 (why?)

Define W1 to be epsilon HOMOGENEOUS, i.e.
for all v in V: W1(v) = epsilon*degree(v) 

Q1: Every MINIMAL-FVS is 2-approximations w.r.t W1. Why?
A1: This is not trivial. See [Becker&Geiger??] or [Williamson??]

The algorithm: iteratively "make" G LEAF-FREE and
subtract W1 as above, where epsilon is selected to be
the largest possible s.t. W >= W1 (i.e. epsilon=Max W(v)/degree(v)).
Induction hyp. implies that reclusive call with W2=W-W1
would return a FVS cover C which is 2-approximation w.r.t. W2.
"Make" C MINIMAL-FVS, thus it is 2-approximation w.r.t. W1 (see Q1).
By the "Local-Ratio Theorem" C is 2-approximation w.r.t. W=W1+W2.

Q2: How to "make" G LEAF-FREE, how to "make" C MINIMAL.

Is there any better way to present the algorithm than by recursion?

+-------------------------------------------------------------------+
| Algorithm BeckerGeiger (G=(V,E),W)                                |
+-------------------------------------------------------------------+
|    If G is a tree return empty set                                |
|    If exists_{x in V}  degree(x) < 2 return BeckerGeiger(G-{x},W) |
|    If exists_{x in V}  W(x) = 0 return {x}+BeckerGeiger(G-{x}, W) |
|    Let epsilon = min_{v in V} W(v)/degree(v)                      |
|    Define W : forall_{x in V} W1(x) = epsilon*degree(x)           |
|    C = BeckerGeiger(G,W-W1)                                       |
|    {"Make C Minimal loop:}                                        |
|    for each x in C, if W1(x) > 0 and C-{x} is FVS for G           |
|       then C=C-{x}                                                |
|    Return C                                                       |
+-------------------------------------------------------------------+


References: to be completed??
[BafBer95]
[BecGei94]
[ChuGoe96]