{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreih5jdbrxorg7etysjwjarwanafqgatijmemj6lntv4faanre3sokq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mohup2pxj5y2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.18225v1",
  "publishedAt": "2026-06-17T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Qi Duan"
  ],
  "textContent": "**Authors:** Qi Duan\n\nWe 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.",
  "title": "Directed Reachability-Preserving Minimum Edge Cut: Approximation and Planar Hardness"
}