Recursive Algorithm
Algorithm RCA (
G
,
n
)
{
G
has
n
vertices}
repeat
twice
randomly contract
G
to
n
/
2
½
vertices
RCA(
G
,
n
/2
1/2
)
(50-50 chance of avoiding min-cut)
