I do not know how to solve the following problem:

Given a directed graph $G$ with a two nodes $s,t \in V(G)$ find a cut $(S,T)$ with $s \in S$ and $t \in T$ such that $(S,T)$ has the minimum number of edges with the "reverse edges", i.e. the edges in $(T,S)$, also counted.

I realise that, when the reverse edges are not taken into account, this problem can be reduced to the problem of finding the min cut with the least edges in an arbitrary flow network, which was already discussed here, by setting all capacities to $1$.

But I do not see how I could include the reverse edges. Could you please give me a hint?

  • 2
    $\begingroup$ It sounds like if you use the max flow algorithm, the flow is allowed to run both forwards and backwards. Kind of like the edges are non-directed? $\endgroup$
    – Pål GD
    Dec 9 '21 at 10:41
  • 2
    $\begingroup$ @PålGD So basically make the graph undirected and find min-cut using max flow algorithm. That should suffice, right? $\endgroup$ Dec 10 '21 at 15:36
  • 1
    $\begingroup$ @InuyashaYagami: Yeah that's right. $\endgroup$
    – 3nondatur
    Dec 10 '21 at 23:57

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.