Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get a Fully Polynomial Randomized Approximation Scheme for it?
[1] Provan, J. Scott, and Michael O. Ball. "The complexity of counting cuts and of computing the probability that a graph is connected." SIAM Journal on Computing 12.4 (1983): 777-788.
The Provan and Ball paper actually shows a 1-1 reduction from bipartite independent sets (BIS) to min st cuts. So an FPRAS for min cuts would imply an FPRAS for #BIS. However, #BIS is not known (and thought unlikely) to have an FPRAS [1][2].
[1] Dyer, Martin, et al. "On the relative complexity of approximate counting problems." International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer, Berlin, Heidelberg, 2000.
[2] Dyer, Martin, Leslie Ann Goldberg, and Mark Jerrum. "An approximation trichotomy for Boolean# CSP." Journal of Computer and System Sciences 76.3-4 (2010): 267-277.
