Connected (s,t)-Vertex Separator Parameterized by Chordality
N. S. Narayanaswamy and N. Sadagopan
Vol. 19, no. 1, pp. 549-565, 2015. Regular paper.
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 δ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.
Submitted: October 2012.
Reviewed: April 2013.
Revised: March 2014.
Reviewed: October 2014.
Revised: November 2014.
Reviewed: April 2015.
Revised: May 2015.
Accepted: October 2015.
Final: October 2015.
Published: November 2015.
Communicated by Martin Fürer
article (PDF)