
## Algorithm  Singleguess(G,J)

Input:   An undirected graph G n and an integer j Output: A feedback verlex set F of size < j, or "Fail" otherwise.

For
. I
Reduce G i -1 to a rich graph G i while placing self loop vertices in F
If G i is the empty graph Return F
Pick an edge e Pick a vertex vi at random from F
F
vi V\ vi V
Ret urn "Fail" Due to Lemma    when SingleGuess(G, j) terminates with a FVS of size j  there is a probability of at least that the output is a minimum FVS
Note that steps   and   in SingleGuess determine a vertex v by first selecting an arbitrary edge and then selecting an arbitrary endpoint of this edge  An equivalent way of achieving the same selection rule is to choose a vertex with probability proportional to its deg ree p Lu e v
.

To see the equivalence of these two selection methods define Γ v to be aset of edges whose one endpoint is v and note that for graphs without self loops

$$p\;\;v$$
ppp  : E I ( v ) ¤E Γ ( v )
This equivalent phrasing of the selection criterion is easier to extend to the weighted case and will be used in the following sections An algonthm for finding a minimum FVS with high probability which we call Repeat-
TED E E S  C A N  n O W  b e  d e s  c r i b e d  a s  f o l l o w s   S  S  t a r t  w i t h  j REPEAT SINGLEGUESS C I
times where c     is a parameter defined by the user  If in one of the iterations a FVS of size < j is found then output this FVS otherwise increase j by one and continue

## Algorithm Repeatedguess(G,C)

Input:   An undirected graph G
and a constant c Output:   A feedback vertex set F
For j
. V
-
Repeat c 'times S INGLEG UESS (G, j)
F
If F is not "Fail" then Return F
End Repeat End For