1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.