2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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$
    – John Kemeny
    Commented Dec 9, 2021 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$
    – Inuyasha Yagami
    Commented Dec 10, 2021 at 15:36
  • 1
    $\begingroup$ @InuyashaYagami: Yeah that's right. $\endgroup$
    – 3nondatur
    Commented Dec 10, 2021 at 23:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.