Hardness of Vertex Separators

Question

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, in which we insist that the size of the resulting components is at most $|V|/2$.

Answer 1

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.

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 by Krauthgamer, Naor and Schwartz.

Answer 2

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.