On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
Pierre Bergé, Wassim Bouaziz, Arpad Rimmel, Joanna Tomasik · SIAM Journal on Discrete Mathematics · 2023
Abstract. The counting of minimum edge [Formula: see text]-cuts in undirected graphs, parameterized by the size [Formula: see text] of these cuts, is FPT. The best performance in the literature is [Formula: see text]. We treat a more general problem of counting minimum [Formula: see text]-cuts composed of vertices instead of edges. We propose an FPT algorithm with running time [Formula: see text]. As it may be applied to the edge version as well, we improve the time complexity of the minimum edge [Formula: see text]-cuts counting.