A tight -approximation for Linear 3-Cut
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan · Society for Industrial and Applied Mathematics eBooks · 2018
We investigate the approximability of the linear 3-cut problem in directed graphs, which is the simplest unsolved case of the linear k-cut problem. The input here is a directed graph D = (V, E) with node weights and three specified terminal nodes s,r,t ∊ V, and the goal is to find a minimum weight subset of non-terminal nodes whose removal ensures that s cannot reach r and t, and r cannot reach t. The problem is approximation-equivalent to the problem of blocking rooted in- and out-arborescences, and it also has applications in network coding and security. The approximability of linear 3-cut has been wide open until now: the best known lower bound under the Unique Games Conjecture (UGC) was 4/3, while the best known upper bound was 2 using a trivial algorithm. In this work we completely close this gap: we present a -approximation algorithm and show that this factor is tight assuming UGC. Our contributions are twofold: (1) we analyze a natural two-step deterministic rounding scheme through the lens of a single-step randomized rounding scheme with non-trivial distributions, and (2) we construct integrality gap instances that meet the upper bound of . Our gap instances can be viewed as a weighted graph sequence converging to a “graph limit structure”.