We study an optimization problem with applications in design and analysis of resilient communication networks: given two vertices
in a graph
), find a vertex set
of minimum cardinality, such that
and its neighborhood constitute an
vertex separator. Although the problem naturally combines notions of graph connectivity and domination, its computational properties significantly differ from these relatives.
In particular, we show that on general graphs the problem cannot be approximated to within a factor of
= 1 / loglog
(if P ≠ NP). This inapproximability result even applies if the subgraph induced by a solution set has the additional constraint of being connected. Furthermore, we give a
-approximation algorithm and study the problem on graphs with bounded node degree. With Δ being the maximum degree of nodes
}, we identify a (Δ + 1) approximation algorithm.