1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ this idea seems to work, thanks. $\endgroup$ – Guy Berkovitz Jan 26 at 14:39

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.