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

Pierre Bergé, Benjamin Mouscadet, Arpad Rimmel +1

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 di…