{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiefckh4okhtpyhefkfv62qmt34lj6tcomnj4pmjc5pbqutvigm2hi",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mof4gq7kpaj2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.14906v1",
  "publishedAt": "2026-06-16T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Qi Duan"
  ],
  "textContent": "**Authors:** Qi Duan\n\nWe 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 basic ``separate while preserve'' requirement that arises in biological intervention design, image analysis with connectivity constraints, and cyber-security attack graph mitigation, where deleting or blocking a node represents preventing the corresponding action, state, or biological entity from participating in a harmful pathway. We prove two results. First, the weighted planar version of three-terminal \\RPMNC{} is NP-complete. The reduction is from \\textsc{Independent Set} on 3-regular Hamiltonian planar graphs and uses a one-sided blocker construction. Second, we give a polynomial-time \\\\(O(\\sqrt n)\\\\)-approximation algorithm for general graphs. The algorithm is based on an exact path--separator identity, a directed split-graph representation of rooted vertex separators, and a root-linear approximation of a monotone submodular separator function.",
  "title": "Three-Terminal Reachability-Preserving Minimum Node Cut: Planar Hardness and a General-Graph \\(O(\\sqrt n)\\)-Approximation"
}