2026/07/22 by Qi Duan
Computer Science · #cs.DS
In the three-terminal Reachability-Preserving Minimum Edge Cut problem, the input is an undirected edge-weighted graph with terminals \(s1,s2,t\). The objective is to delete a minimum-cost set of edges that separates \(t\) from both \(s1\) and \(s2\), while preserving connectivity between \(s1\) and \(s2\). We give a polynomial-time \(O(log n)\)-approximation algorithm. The algorithm uses a probabilistic distribution of cut-dominating decomposition trees. A direct transfer of a connected tree solution to the original graph is not valid because a connected tree cluster may induce a disconnected vertex set in the graph. We overcome this obstruction by expanding every rooted tree cluster into the connected components it induces in the original graph. These components form a node-weighted auxiliary graph. A minimum node-weighted path in this auxiliary graph produces a connected feasible source side. The main structural observation is that the total graph-boundary cost of all connected components of a rooted tree cluster is no greater than the capacity of the corresponding tree edge. This permits the auxiliary path to be compared with a tree cut separating an optimal preserved \(s1\)-\(s2\) path from \(t\). Combining this comparison with the expected \(O(log n)\) cut distortion of the decomposition trees proves the approximation guarantee.