Comment by eutectic

Also, the problem is to find a global min-cut, which requires all-pairs max flow.