Abstract: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 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.
From: Qi Duan [view email]
[v1]
Fri, 12 Jun 2026 19:24:32 UTC (11 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。