3
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\begingroup$ At least the problem is P by running O(E^2) max-flow algorithm on unweighted graph. $\endgroup$
    – Saeed
    Feb 14, 2015 at 17:42
  • 1
    $\begingroup$ It be nice to know the motivation behind the problem. $\endgroup$
    – Chao Xu
    Feb 18, 2015 at 15:20
  • 1
    $\begingroup$ 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) $\endgroup$
    – Chao Xu
    Feb 18, 2015 at 19:42

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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