Are there any non-trivial bounds on the space complexity of global minimum cut? The problem is known to be in $\mathsf{RNC}$. Is anything known about containment in either $\mathsf{L}$ or $\mathsf{NL}$?

Such a bound seems unlikely for the space-complexity of s-t minimum cut given that maximum flow is $\mathsf{P}$-complete.

  • 1
    $\begingroup$ Is global mincut in NC? I think it is only known to be in RNC. Look in Karger's paper dl.acm.org/citation.cfm?id=331608. $\endgroup$ Sep 2 '19 at 16:56
  • $\begingroup$ Sorry, you are absolutely correct (updated to RNC in the original post). I don't know of any NC algorithms for global min cut. The fastest deterministic sequential algorithm seems to be due to Kawarabayashi and Thorup (dl.acm.org/citation.cfm?id=2746588). $\endgroup$
    – xal
    Sep 2 '19 at 20:44

Your Answer

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

Browse other questions tagged or ask your own question.