Leighton, Rao presented an $O(\log n)$ approximation algorithm for directed and undirected balanced vertex separator. Agarwal, Charikar, Makarychev, Makarychev improved this approximation factor of directed balanced vertex separator to $O(\sqrt{\log n})$.

Is there an $O(\log \mathsf{opt})$ approximation algorithm for directed balanced vertex separator, where $\mathsf{opt}$ is the optimal size of the directed balanced vertex separator ?

I would appreciate any references/pointers.



Your Answer

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