Recall that by definition F 2 is the minimum FVS in the branchy graph G 2 obtained from G 1 \   v 1     We get

$$E\;\;w\;\;F^{*}\;\;\;\geq\;E_{1}\;\;w\;\;v\;\;v\in\;F_{1}^{*}$$
$$E\;\;u\;\;F_{2}^{*}$$

because the right hand side is the expected weight of the output F assuming the algorithm finds a minimum FVS on G 2 and just needs to select one additional vertex while the left hand side is the unrestricted expectation  By repeating this argument we get

$E$$w$$F^{*}$$\geq$$1$$E$$w$$F_{2}^{*}$$\geq$$\cdot$$\cdot$$\geq$$\sum_{i=1}^{k}$
# Using $\sum_{i\quad i\quad}\sum_{i\quad i}\leq\max_{i\quad i\quad i}\leq\quad$ we obtain . 
$$\begin{array}{r c l c r}{E~w~F}&{\leq}&{\cdot~E~w~F^{*}}\end{array}$$
Hence  E  w  F   <     w  F*   as claimed   □
The proof that SINGLEGUESS(G, k) outputs a FVS whose expected size is no more than  k  Theorem    where k is the size of a minimum FVS is analogous to the proof of Theorem in the following sense We assign a weight to all vertices and replace the reference to Lemma    by a reference to the following claim   If F is a FVS of a rich graph G
then Evev v < Ever v The proof of this claim is identical to the proof of Lemma except that instead of using Lemma we use Lemma

## 3.3 The Practical Algorithm

In previous sections we presented several algorithms for finding minimum FVS with high probability The description of these algonthms was geared towards analysis  rather than as a prescription to a programmer In particular the number of iterations used within REPEATEDWGUESSI(G, c, k) is not changed as the algorithm is run with j    k  This feature alowed us to regard each call to SINGLEWGUESSI(G, j) made by REPEATEDWGUESSI as an independent process  Furthermore  there is a small probability for a very long run even w hen the size of the minimum FVS is small We now slightly modify RepeatedWGuessI to obtain an algorithm termed WRA
which does not suffer from these deficiencies  The new algorithm works as follows  Repeat SINGLEWGUESSI(G, V ) for m n Max, c "(F) iterations where w F is the weight of the lightest WFVS found so far and Max is some specified constant determining the maximum number of iterations of SINGLEWGUESSI

## Algorithm Wra(G, C, Max)

Input:   An undirected weighted graph G  V, E   and constants Max and c Output:   A feedback vertex set F
SINGLEWGUESSI (G, V)
F
M   m n Max, c w(F)
While < M do F'         S INGLE WG UESS I ( G ,  V  )
If w  F ′  ≤  w  F   t he n