<p>In the edge setting, the problem you're referring to is the bisection problem, and the size of such a minimum edge is called the bisection width. There's a ton of research on this problem, and the best known approximation for the problem is $O(\log n)$ <a href="http://doi.acm.org/10.1145/1374376.1374415">by Racke</a>.</p>

<p>A good review of the known work on this problem (which connects to sparsest cut, spreading metrics, and even the unique games conjecture) is in <a href="http://portal.acm.org/citation.cfm?id=1496872">this recent paper on generalizations of bisection width</a> by Krauthgamer, Naor and Schwartz.</p>

CC BY-SA 2.5
2010-09-23T19:41:50.560Z
2010-09-23T19:41:50.560Z
Suresh Venkat
<p>The approximability of the separator question in the sense you want is closely related to the approximability of the uniform sparsest cut problem. An $O(\sqrt{\log n})$-factor approximation was obtained by Arora-Rao-Vazirani improving the $O(\log n)$ of
Leighton and Rao; they did this for the edge case. Agrawal-Charikar-Makarychev-Makarychev used the result to obtain similar bound for directed sparsest cut (if one is interested in vertex bipartition cuts). Feige-Hajiaghayi-Lee at the same time obtained a similar bound again via ARV for vertex separators (and also pointed out that treewidth can be approximated within the same factor). One should note that there is another notion of sparsest cut in directed graphs for which Chuzhoy-Khanna showed hardness results in the non-uniform case but I am not sure about the uniform case.  I think super-constant hardness results are known for (uniform) sparsest cut under UGC but I am not sure.</p>

CC BY-SA 3.0
2011-12-03T03:03:21.073Z
2011-12-03T03:03:21.073Z
Chandra Chekuri
<p>For a given graph $G$, the Separator Problem asks whether a vertex or edge set of small cardinality (or weight) exists whose removal partitions $G$ into two disjoint graphs of approximately equal sizes. This is called the Vertex Separator Problem when the removed set is a vertex set, and the Edge Separator Problem when it is an edge set. Both problems are NP-complete for general unweighted graphs. What is the best known hardness of approximating vertex separator ? Is a PTAS ruled out ? What are the best known hardness results in the directed setting ?</p>

<p><strong>Correction</strong> : The following links and answers did not help me because I did not state my question correctly. My question is related to the following theorem of Leighton-Rao :</p>

<p><em>Theorem</em> : There exists a polynomial time algorithm that, given a graph $G(V,E)$ and a set $W \subseteq V$, finds a $\frac{2}{3}$ vertex separator $S \subseteq V$ of $W$ in $G$ of size $O(w.{\log}n)$, where $w$ is the minimum size of a $\frac{1}{2}$-vertex separator of $W$ in $G$.</p>

<p>Given a graph $G(V,E)$ and a set $W \subseteq V$, I want to find a $\delta$-vertex separator (where $\frac{1}{2} \leq \delta \leq 1$ is a constant) of size $w$, where $w$ is the minimum size of a $\frac{1}{2}$-vertex separator of $W$ in $G$. What is the best known hardness of this problem ? The above theorem gives an $O({\log}n)$ approximation for this problem.</p>

<p>Note that I am allowing constant factor blow-up in the size of the resulting components after removing the separator, but I want to minimize the size of the separator itself. The links mentioned in the comments point to <a href="http://www.csc.kth.se/~viggo/wwwcompendium/node96.html" rel="noreferrer">minimum b-vertex separator</a>, in which we insist that the size of the resulting components is at most $|V|/2$.</p>

CC BY-SA 2.5
2010-12-01T21:25:52.937Z
I'm interested in this question too, did you find anything since then?
Yaroslav Bulatov
CC BY-SA 2.5
2010-12-05T04:46:40.053Z
@Yaroslav : No. Unfortunately I could not find any hardness results for this particular problem.
Shiva Kintali
CC BY-SA 2.5
2010-09-24T10:32:22.223Z
I realized that my previous comments were unnecessarily harsh.  I removed them.  I leave only links in those comments: the [vertex version](http://www.csc.kth.se/~viggo/wwwcompendium/node96.html) and the [edge version](http://www.csc.kth.se/~viggo/wwwcompendium/node95.html) in the Compendium of NP Optimization Problems.
Tsuyoshi Ito
<cc.complexity-theory><approximation-hardness>
Hardness of Vertex Separators
Shiva Kintali
# Hardness of Vertex Separators

(Asked by: username_0 on 2010-09-23)

For a given graph $G$, the Separator Problem asks whether a vertex or edge set of small cardinality (or weight) exists whose removal partitions $G$ into two disjoint graphs of approximately equal sizes. This is called the Vertex Separator Problem when the removed set is a vertex set, and the Edge Separator Problem when it is an edge set. Both problems are NP-complete for general unweighted graphs. What is the best known hardness of approximating vertex separator ? Is a PTAS ruled out ? What are the best known hardness results in the directed setting ?

**Correction** : The following links and answers did not help me because I did not state my question correctly. My question is related to the following theorem of Leighton-Rao :

*Theorem* : There exists a polynomial time algorithm that, given a graph $G(V,E)$ and a set $W \subseteq V$, finds a $\frac{2}{3}$ vertex separator $S \subseteq V$ of $W$ in $G$ of size $O(w.{\log}n)$, where $w$ is the minimum size of a $\frac{1}{2}$-vertex separator of $W$ in $G$.

Given a graph $G(V,E)$ and a set $W \subseteq V$, I want to find a $\delta$-vertex separator (where $\frac{1}{2} \leq \delta \leq 1$ is a constant) of size $w$, where $w$ is the minimum size of a $\frac{1}{2}$-vertex separator of $W$ in $G$. What is the best known hardness of this problem ? The above theorem gives an $O({\log}n)$ approximation for this problem.

Note that I am allowing constant factor blow-up in the size of the resulting components after removing the separator, but I want to minimize the size of the separator itself. The links mentioned in the comments point to [minimum b-vertex separator](http://www.csc.kth.se/~viggo/wwwcompendium/node96.html), in which we insist that the size of the resulting components is at most $|V|/2$.

**Tags:** cc.complexity-theory, approximation-hardness

> **Comments:**
> **username_2**: I realized that my previous comments were unnecessarily harsh.  I removed them.  I leave only links in those comments: the [vertex version](http://www.csc.kth.se/~viggo/wwwcompendium/node96.html) and the [edge version](http://www.csc.kth.se/~viggo/wwwcompendium/node95.html) in the Compendium of NP Optimization Problems.  
> **username_1**: I'm interested in this question too, did you find anything since then?  
> **username_0**: @Yaroslav : No. Unfortunately I could not find any hardness results for this particular problem.  

---

## 2 answers

### Answer by username_3 on 2010-09-23. Score: 9

In the edge setting, the problem you're referring to is the bisection problem, and the size of such a minimum edge is called the bisection width. There's a ton of research on this problem, and the best known approximation for the problem is $O(\log n)$ [by Racke](http://doi.acm.org/10.1145/1374376.1374415).

A good review of the known work on this problem (which connects to sparsest cut, spreading metrics, and even the unique games conjecture) is in [this recent paper on generalizations of bisection width](http://portal.acm.org/citation.cfm?id=1496872) by Krauthgamer, Naor and Schwartz.


---

### Answer by username_4 on 2011-12-03. Score: 5

The approximability of the separator question in the sense you want is closely related to the approximability of the uniform sparsest cut problem. An $O(\sqrt{\log n})$-factor approximation was obtained by Arora-Rao-Vazirani improving the $O(\log n)$ of
Leighton and Rao; they did this for the edge case. Agrawal-Charikar-Makarychev-Makarychev used the result to obtain similar bound for directed sparsest cut (if one is interested in vertex bipartition cuts). Feige-Hajiaghayi-Lee at the same time obtained a similar bound again via ARV for vertex separators (and also pointed out that treewidth can be approximated within the same factor). One should note that there is another notion of sparsest cut in directed graphs for which Chuzhoy-Khanna showed hardness results in the non-uniform case but I am not sure about the uniform case. I think super-constant hardness results are known for (uniform) sparsest cut under UGC but I am not sure.


---

