Consider a directed, weakly connected bipartite graph $G = (U, V, E)$ where $U$ and $V$ are sets comprising the nodes of $G$, and $E \subseteq U \times V$ is the set of edges. The task is to find a minimum directed cut, say $C \subseteq E$, such that the graph $G = (U, V, E - C)$ consists of two disconnected bipartite graphs each of which are (1) not edgeless, and (2) weakly connected. The cut $C$ is directed in the sense that all edges in $C$ originate from the same bipartite subgraph, and minimum in the sense that it has the lowest cardinality possible.

Is this problem studied? If so, what is the computational complexity of the best known algorithm that solves it? If not, original algorithm ideas are more than welcome!

  • At least the problem is P by running O(E^2) max-flow algorithm on unweighted graph. – Saeed Feb 14 '15 at 17:42
  • 1
    It be nice to know the motivation behind the problem. – Chao Xu Feb 18 '15 at 15:20
  • 1
    Using @Saeed's observation, your problem seems like a (harder) variant of the minimum vertex cover split problem described in section 3. This paper might inspire something with faster running time. (but this is a long stretch, as you really want to find a cut that separate both bipartition instead of just one) – Chao Xu Feb 18 '15 at 19:42

I'll provide a naive approach which give $O(m^2 \cdot max_f)$ running time but shows the problem is P. First turn the graph to undirected graph. Suppose one edge is in first graph and the other in the second graph, contract both of them and name them $s,t$. We can find a minimum edge cut that separates s and t in time max_f which is a running time of best maximum flow algorithm on unit weight graph. We run this algorithm for all possible pair of edges. But why this works? trivially there is no smaller cut and the two sides are not edgeless. On the other hand if a graph G is connected minimum edge cut C between two vertices s, t always cuts the graph into two connected subgraphs.

This problem was studied in the following paper.

Abdol-Hossein Esfahanian, S.Louis Hakimi, On computing a conditional edge-connectivity of a graph, Information Processing Letters, Volume 27, Issue 4, 1988, Pages 195-199, ISSN 0020-0190, http://dx.doi.org/10.1016/0020-0190(88)90025-7.

The idea is identical to Saeed's method, contract pairs of edges and find a min-cut. However, one can be more careful and show $O(m)$ pairs are sufficient.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.