Directed Reachability-Preserving Minimum Edge Cut: Approximation and Planar Hardness

Qi Duan

We study a directed version of the three-terminal reachability-preserving minimum edge cut problem. Given a directed graph $G=(V,A)$ with arc costs and terminals $s_1,s_2,t$, the o…