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]