@article{doi:10.1137/21M1398203,
author = {Berg\'{e}, Pierre and Bouaziz, Wassim and Rimmel, Arpad and Tomasik, Joanna},
title = {On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts},
journal = {SIAM Journal on Discrete Mathematics},
volume = {37},
number = {2},
pages = {964-996},
year = {2023},
doi = {10.1137/21M1398203},

URL = { 
    
        https://doi.org/10.1137/21M1398203
    
    

},
eprint = { 
    
        https://doi.org/10.1137/21M1398203
    
    

}
,
    abstract = { Abstract. The counting of minimum edge \((S,T)\)-cuts in undirected graphs, parameterized by the size \(p\) of these cuts, is FPT. The best performance in the literature is \(O^*(2^{O(p^2)})\). We treat a more general problem of counting minimum \((S,T)\)-cuts composed of vertices instead of edges. We propose an FPT algorithm with running time \(O^* (2^{O(p\log p)} )\). As it may be applied to the edge version as well, we improve the time complexity of the minimum edge \((S,T)\)-cuts counting. }
}