A tight $\sqrt{2}$-approximation for Linear 3-Cut

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan


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\in 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 $\sqrt{2}$-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 \emph{non-trivial} distributions, and (2) we construct integrality gap instances that meet the upper bound of $\sqrt{2}$. Our gap instances can be viewed as a weighted graph sequence converging to a ``graph limit structure''.

Bibtex entry:

AUTHOR = {B{\'e}rczi, Krist{\'o}f and Chandrasekaran, Karthekeyan and Kir{\'a}ly, Tam{\'a}s and Madan, Vivek},
TITLE = {A tight $\sqrt{2}$-approximation for Linear 3-Cut},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2017},
NUMBER = {TR-2017-10}

Last modification: 13.3.2018. Please email your comments to Tamás Király!