On the Complexity of Connected $(s,t)$-Vertex Separator

N. S. Narayanaswamy, N. Sadagopan

We show that minimum connected $(s,t)$-vertex separator ($(s,t)$-CVS) is $\Omega (lo{g}^{2-\epsilon }n)$-hard for any $\epsilon >0$ unless NP has quasi-polynomial Las-Vegas algorithms. i.e., for any $\epsilon >0$…