Fixed-parameter tractability of counting small minimum $(S,T)$-cuts

Understand

The parameterized complexity of counting minimum cuts stands as a natural question because Ball and Provan showed its #P-completeness.

• For any undirected graph $G=(V,E)$ and two disjoint sets of its vertices $S,T$, we design a fixed-parameter tractable algorithm which counts minimum edge $(S,T)$-cuts parameterized by their size $p$.
• Our algorithm operates on a transformed graph instance.
• This transformation, called drainage, reveals a collection of at most $n=\left| V \right|$ successive minimum $(S,T)$-cuts $Z_i$.