Qi Duan

An O(log n)-Approximation for Three-Terminal Reachability-Preserving Minimum Edge Cut

In the three-terminal Reachability-Preserving Minimum Edge Cut problem, the input is an undirected edge-weighted graph with terminals \(s_1,s_2,t\). The objective is to delete a minimum-cost set of edges that separates \(t\) from both \(s_1\) and \(s_2\), while preserving connectivity between \(s_1\) and \(s_2\). We gi...