I'm having problem understanding the min weight st-cut integer programming in this wiki page: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

In the min-cut dual part, it has

$$d_{ij}-p_i+p_i \geq 0 \;\; \forall (i,j) \in E$$ where $d_{ij}$ is binary: 1 if the edge is selected in st-cut 0 otherwise. p_i is 1 if vertex i is in the same side as s and 0 if in the same side as p. (you can read the original wiki for more information).

I'm not able to understand how this constraint will make this IP work.

  • $\begingroup$ look at every cases $p_i - p_j = 0$ or $1$ or $-1$ $\endgroup$ – reuns Jan 21 '16 at 10:49
  • $\begingroup$ @user1952009 I did, but I don't understand why having this constraint to find the min weight st-cut $\endgroup$ – Yilun Zhang Jan 21 '16 at 17:25

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.