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

We show that minimum connected $(s,t)$-vertex separator ($(s,t)$-CVS) is $Ω(log^{2-ε}n)$-hard for any $ε>0$ unless NP has quasi-polynomial Las-Vegas algorithms. i.e., for any $ε>0$ and for some $δ>0$, $(s,t)$-CVS is unlikely to have $δ.log^{2-ε}n$-approximation algorithm. We show that $(s,t)$-CVS is NP-complete on graphs with chordality at least 5 and present a polynomial-time algorithm for $(s,t)$-CVS on bipartite chordality 4 graphs. We also present a $\lceil\frac{c}{2}\rceil$-approximation algorithm for $(s,t)$-CVS on graphs with chordality $c$. Finally, from the parameterized setting, we show that $(s,t)$-CVS parameterized above the $(s,t)$-vertex connectivity is $W[2]$-hard.

No reviews yet.

No comments yet.