<p>Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph?</p>

<p>I have a large bipartite graph with $|V_1|$ = 40M and $|V_2|$ = 150K and want to remove vertices from $V_1$ to disconnect the graph.  Obviously, with a graph this large, I need a fairly efficient algorithm.</p>

<p>Does anyone have suggestions?</p>

CC BY-SA 3.0
2013-03-29T08:14:33.170Z
one way is to connect each pair of neighbors $x,y\in N(v)\cap V_1$ for each vertex $v\in V_2$, and then find a minimum separator in the new graph.
Yixin Cao
CC BY-SA 3.0
2013-09-15T12:54:43.403Z
A suggestion, but without theoretical backing: Pick a vertex or small set of vertices at random and run a breadth-first search starting there. Note that each "layer" (set of vertices at distance $d$ from the original vertex/set) either lies entirely within $V_1$ or within $V_2$, and furthermore each layer is a separating set (for the vertices before it in the BFS and the vertices after it). Pick the smallest layer that lies within $V_1$. Maybe repeat this a couple times with different initial vertices/sets.
usul
CC BY-SA 3.0
2013-09-15T12:56:06.143Z
Two more: (1) find a min cut and take all the $V_1$ vertices attached to it.  (2) Find a maximum matching, remove all the $V_1$ vertices in it (adding them to your separating set), and repeat on the remaining graph.
usul
<ds.algorithms><graph-theory><co.combinatorics><approximation-algorithms>
Bipartite vertex separator
nomad
# Bipartite vertex separator

(Asked by: username_0 on 2013-03-29)

Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V\_1, V\_2, E)$ where the selected vertices are constrained to come from one partition of the graph?

I have a large bipartite graph with $|V\_1|$ = 40M and $|V\_2|$ = 150K and want to remove vertices from $V\_1$ to disconnect the graph. Obviously, with a graph this large, I need a fairly efficient algorithm.

Does anyone have suggestions?

**Tags:** ds.algorithms, graph-theory, co.combinatorics, approximation-algorithms

> **Comments:**
> **username_1**: one way is to connect each pair of neighbors $x,y\in N(v)\cap V_1$ for each vertex $v\in V_2$, and then find a minimum separator in the new graph.  
> **username_2**: A suggestion, but without theoretical backing: Pick a vertex or small set of vertices at random and run a breadth-first search starting there. Note that each "layer" (set of vertices at distance $d$ from the original vertex/set) either lies entirely within $V_1$ or within $V_2$, and furthermore each layer is a separating set (for the vertices before it in the BFS and the vertices after it). Pick the smallest layer that lies within $V_1$. Maybe repeat this a couple times with different initial vertices/sets.  
> **username_2**: Two more: (1) find a min cut and take all the $V_1$ vertices attached to it.  (2) Find a maximum matching, remove all the $V_1$ vertices in it (adding them to your separating set), and repeat on the remaining graph.  

---

## 0 answers

