# Finding the cut with the minimum number of edges (including reverse ones)

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?

• 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? Dec 9 '21 at 10:41
• @PålGD So basically make the graph undirected and find min-cut using max flow algorithm. That should suffice, right? Dec 10 '21 at 15:36
• @InuyashaYagami: Yeah that's right. Dec 10 '21 at 23:57