---
# System prepended metadata

title: Weighted min-cut (Distributed implementation)

---

# Weighted min-cut (Distributed implementation)

    
## Spanning tree is a path

We are looking at the following bipartite interval problem: Consider a subsequence $S$ of $L$ ($|S| = k$) and a subsequence $T$ of $R$. Can we find 2-respecting min-cut where one of the respected edge is in $S$ and the other is in $R$? **Goal**. The complexity should be $O(k + D)$. 





