| Focus on Small Cuts |
|
|
|
|
|
|
|
|
|
| l | Fact: FAIL(p) >
pc |
|||||||
| l | Theorem:
if pc=1/n(2+d) then |
|||||||
| Pr[>a-mincut fails]< n-ad |
||||||||
| l | Corollary: FAIL(p) » Pr[£ a-mincut fails], |
|||||||
| where a=1+2/d |
||||||||
| l | Recall:
O(n2a) a-mincuts |
|||||||
| l | Enumerate with
RCA, run DNF counting |
|||||||