3
$\begingroup$

Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e.

So, I tried couple of steps, first, I know I must saturate $e$ so it could be in any min-cut. I tried to add a supersource that connects to $u$ (with infinite capacity) and a supersink that connects to $v$. But that will only saturate $e$ if it is not yet been saturated, not force it to be in a min cut $s,t$. I also thought maybe to reduce an epsilon from the capacity of $e$, but I am not sure if it is enough.

I also tried to connect the supersource to all of u neighbors and the supersink to all of v neighbors and then reduce an epsilon from e. Again I don’t know if that’s enough.

I’m not sure how to continue (or if i can) from here or if I’m missing something.

$\endgroup$
1
$\begingroup$

Remove $u$ and $v$ (as well as all edges connected to them), and for any removed edge $(u,x)$, add an edge from $s$ to $x$ with the same capacity; for any removed edge $(y,v)$, add an edge from $y$ to $t$ with the same capacity. Now find a min cut in this new graph. The partition of nodes in this cut suggests a min cut among those including $e$ in the original graph.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.