# Space complexity of global minimum cut

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.

• 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. Sep 2 '19 at 16:56
• 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).
– xal
Sep 2 '19 at 20:44