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

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

2011-11-08

arxiv.org/abs/1111.1814v1

Computer Science

Discrete Mathematics

Scientific paper

We show that minimum connected $(s,t)$-vertex separator ($(s,t)$-CVS) is $\Omega(log^{2-\epsilon}n)$-hard for any $\epsilon >0$ unless NP has quasi-polynomial Las-Vegas algorithms. i.e., for any $\epsilon >0$ and for some $\delta >0$, $(s,t)$-CVS is unlikely to have $\delta.log^{2-\epsilon}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.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Connected (s, t)-Vertex Separator does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of Connected (s, t)-Vertex Separator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Connected (s, t)-Vertex Separator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-53136