Connected (s; t)-vertex separator parameterized by chordality

We investigate the complexity of _nding a minimum connected (s; t)-vertex separator ((s; t)-CVS) and present an interesting chordality di-chotomy: we show that (s; t)-CVS is NP-complete on graphs of chordal-ity 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 δlog2-∊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.