Minimum number of edges to remove to disconnect two node sets $A$ and $B$ in a directed graph

Question

We have directed graph $G$ (not necessarily a DAG), two disjoint sets $A$, $B$, of vertices.
I need to plan an algorithm returning the minimum number of edges that need to be removed, such that there will be no path from any node in $A$, to any node in $B$ and vice versa.

I had the idea using max flow min-cut to find the minimum number of edges needing to be removed such that there won't be a path from $A$ to $B$, and then using the algorithm again on $B$ (so there won't be a path to $A$).
The problem is that the sum of these minimum number of edges isn't necessarily the "global" minimum.

Does there even exist such an algorithm running in polynomial time?

Answer 1

You could try reducing your problem to the directed $s$-$t$ cut problem.

That is, given an instance $G=(V,A)$ of your problem, construct a graph $H$ that is initially a copy of $G$. Then, add to $H$ two new vertices $x$ and $y$, add an arc from $x$ to each $a \in A$ and from $y$ to each $b \in B$; all with a large weight (say $m+1$, where $m = |A|$). The intuition is that an $s$-$t$ cut of $H$ will never use any of the arcs originating from $x$ or $y$ since they are so heavy, but instead only use arcs present in $G$.

You should try to formalize this intuition, i.e., (i) show that the reduction is correct and (ii) show that there is an efficient algorithm for directed $s$-$t$ cut. If both check out, you are done.