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]