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:
@techreport{egres-17-10,
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 www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2017}, |
NUMBER | = | {TR-2017-10} |