AI summaryⓘ
The authors study a problem where, given a directed graph with three special points (s1, s2, and t), you want to remove the cheapest set of edges so that you can still reach s2 from s1 but cannot reach t from s1 anymore. They provide a mathematical formulation for this problem and create approximation algorithms that work well, especially on certain types of graphs. For general directed graphs, their method achieves an approximation factor related to the square root of a graph parameter, and for acyclic graphs, the approximation also depends on path length. Additionally, they prove the problem is very hard to solve exactly on directed planar graphs, even without cycles, using a reduction from a known difficult problem.
directed graphminimum edge cutreachabilityapproximation algorithmplanar graphacyclic graphpolymatroidNP-hardnessgraph reachabilityrooted directed cut
Abstract
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 one-way directed RPMEC problem asks for a minimum-cost set of arcs whose deletion preserves the reachability $s_1\leadsto s_2$ while destroying the reachability $s_1\leadsto t$. We first give a path--cut formulation in terms of a rooted directed cut function. Using a root-linear approximation for the associated polymatroid, we obtain an $O(\sqrt r)$-approximation, where $r$ is the number of relevant vertices with positive singleton cut value. In particular this gives an $O(\sqrt n)$-approximation in general directed graphs. For acyclic directed graphs, we give an additional singleton-length algorithm and obtain an $O(\min\{\sqrt r,h\})$ guarantee, where $h$ is the maximum number of relevant vertices on an $s_1$-$s_2$ path. Finally, we prove that directed planar RPMEC is NP-hard, even on acyclic planar digraphs with nonnegative costs, by reducing from independent set on cubic planar graphs through a finite-bimodal directed node-cut construction and a planar node-to-edge split.