Three-Terminal Reachability-Preserving Minimum Node Cut: Planar Hardness and a General-Graph \(O(\sqrt n)\)-Approximation (opens in new tab)

We study the three-terminal reachability-preserving minimum node cut problem (\RPMNC). The input is an undirected graph \(G=(V,E)\), nonnegative vertex weights on nonterminal vertices, two protected terminals \(s_1,s_2\), and a target terminal \(t\). The goal is to delete a minimum-weight set of nonterminal vertices so that \(t\) is disconnected from the protected terminals, while \(s_1\) and \(s_2\) remain connected. This problem captures a bas...