

![0_image_0.png](0_image_0.png)

Theorem 3  Let G be a weighted undirected graph and c ≥   be a constant. a) The algorithm RepeatedWGuessl(G, c, k) outputs after O c *kn  steps a minimum WFVS with probability at least l c 6*, where k is the minimal size of a minimum weight FVS of G and n is the number of vertices. b) The algorithm SingleWGuessII(G,k) outputs a feedback vertex set whose expected weight is no more than six times the weight of a minimum weight FVS.

The proof of each part requires a preliminary lemma Lemma 4  Let G     V, E   be a branchy graph, F be a feedback vertex set of G and V\ F. Let Ex denote the set of edges in E whose endpoints are all vertices in and EFx denote the set of edges in G that connect vertices in F with vertices in
. Then, Ex < EF x ·
Proof.   Let by an edge between its neighbors and denote the resulting set of edges between vertices in by E x , and between vertices in     and F by E x x ,  The proof of Lemma   shows that

$$E_{X}^{b},\ \leq\ E_{F,X}^{b},$$

Since every linkpoint in has both neighbors in the set 

$$E_{X}~\leq~\cdot~E_{X}^{b},~~~\mathrm{and}~~~E_{F,X}~~~~~~~~E_{F,X}^{b}$$

Hence  Ex ≤  · E F x An immediate consequence of Lemma is that the probability of randomly choosing an edge that has at least one endpoint that belongs to a FVS is greater or equal Thus selecting a vertex at random from a randomly selected edge has a probability of at least to belong to a FVS  Consequently if the algorithm terminates after c  k iterations  with a WFVS of size k  there is a probability of at least l c 6 k that the output is a minimum WFVS of size at most k  This proves part  a  of Theorem Note that since k is not known in advance  we use RepeatedWGuessI(G, c, j) with increasing values of j until a FVS is found say when j J When such a set is found it is still possible that there exists a WFVS with more than J vertices that has a smaller weight than the one found This happens when k J However among the WFVSs of size at most J the algorithm finds one with minimum weight with high probability The second part requires the following lemma