<p>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. </p>

CC BY-SA 3.0
2015-02-18T12:16:00.637Z
2015-02-18T12:16:00.637Z
Saeed
<p>This problem was studied in the following paper. </p>

<p>Abdol-Hossein Esfahanian, S.Louis Hakimi, <a href="http://www.sciencedirect.com/science/article/pii/0020019088900257" rel="nofollow">On computing a conditional edge-connectivity of a graph</a>, Information Processing Letters, Volume 27, Issue 4, 1988, Pages 195-199, ISSN 0020-0190, <a href="http://dx.doi.org/10.1016/0020-0190(88)90025-7" rel="nofollow">http://dx.doi.org/10.1016/0020-0190(88)90025-7</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2016-04-25T02:41:59.683Z
2016-04-25T02:41:59.683Z
Chao Xu
<p>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 <em>a minimum</em> 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.</p>

<p>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!</p>

CC BY-SA 3.0
2015-02-14T17:42:39.213Z
At least the problem is P by running O(E^2) max-flow algorithm on unweighted graph.
Saeed
CC BY-SA 3.0
2015-02-18T15:20:40.313Z
It be nice to know the motivation behind the problem.
Chao Xu
CC BY-SA 3.0
2015-02-18T19:42:22.737Z
Using @Saeed's observation, your problem seems like a (harder) variant of the [minimum vertex cover split problem described in section 3](http://dl.acm.org/citation.cfm?id=338899). 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
<ds.algorithms><reference-request><graph-theory><graph-algorithms>
Finding a minimum directed cut that splits a weakly connected bipartite graph into two such non-edgeless graphs
iheap
# Finding a minimum directed cut that splits a weakly connected bipartite graph into two such non-edgeless graphs

(Asked by: username_0 on 2015-02-12)

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!

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: At least the problem is P by running O(E^2) max-flow algorithm on unweighted graph.  
> **username_2**: It be nice to know the motivation behind the problem.  
> **username_2**: Using @username_1's observation, your problem seems like a (harder) variant of the [minimum vertex cover split problem described in section 3](http://dl.acm.org/citation.cfm?id=338899). 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)  

---

## 2 answers

### Answer by username_1 on 2015-02-18. Score: 2

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.


---

### Answer by username_2 on 2016-04-25. Score: 1

This problem was studied in the following paper.

Abdol-Hossein Esfahanian, S.Louis Hakimi, [On computing a conditional edge-connectivity of a graph](http://www.sciencedirect.com/science/article/pii/0020019088900257), 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 username_1's method, contract pairs of edges and find a min-cut. However, one can be more careful and show $O(m)$ pairs are sufficient.


---

