<p>Are there any non-trivial bounds on the space complexity of global minimum cut? The problem is known to be in <span class="math-container">$\mathsf{RNC}$</span>. Is anything known about containment in either <span class="math-container">$\mathsf{L}$</span> or <span class="math-container">$\mathsf{NL}$</span>?</p>

<p>Such a bound seems unlikely for the space-complexity of s-t minimum cut given that maximum flow is <span class="math-container">$\mathsf{P}$</span>-complete.</p>

CC BY-SA 4.0
2019-09-02T16:56:28.173Z
Is global mincut in NC? I think it is only known to be in RNC. Look in Karger's paper https://dl.acm.org/citation.cfm?id=331608.
Chandra Chekuri
CC BY-SA 4.0
2019-09-02T20:44:13.430Z
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 (https://dl.acm.org/citation.cfm?id=2746588).
xal
<dc.parallel-comp><space-complexity><max-flow-min-cut>
Space complexity of global minimum cut
xal
# Space complexity of global minimum cut

(Asked by: username_0 on 2019-09-02)

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.

**Tags:** dc.parallel-comp, space-complexity, max-flow-min-cut

> **Comments:**
> **username_1**: Is global mincut in NC? I think it is only known to be in RNC. Look in Karger's paper https://dl.acm.org/citation.cfm?id=331608.  
> **username_0**: 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 (https://dl.acm.org/citation.cfm?id=2746588).  

---

## 0 answers

