Connected (s,t)-Vertex Separator Parameterized by Chordality

Abstract

We investigate the complexity of finding a minimum connected (s,t)-vertex separator ((s,t)-CVS) and present an interesting chordality dichotomy: we show that (s,t)-CVS is NP-complete on graphs of chordality at least 5 and present a polynomial-time algorithm for (s,t)-CVS on chordality 4 graphs. Further, we show that (s,t)-CVS is unlikely to have δlog^2−ϵn-approximation algorithm, for any ϵ > 0 and for some δ > 0, unless NP has quasi-polynomial Las Vegas algorithms. On the positive-side of approximation, we present a ⎡c/2⎤-approximation algorithm for (s,t)-CVS on graphs with chordality c ≥ 3. Finally, in the parameterized setting, we show that (s,t)-CVS parameterized above the (s,t)-vertex connectivity is W[2]-hard.