TY - GEN

T1 - A tight √2-approximation for Linear 3-cut

AU - Bérczi, Kristóf

AU - Chandrasekaran, Karthekeyan

AU - Király, Tamás

AU - Madan, Vivek

N1 - Publisher Copyright:
© Copyright 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - 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 2 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 inand 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 p 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 non-trivial distributions, and (2) we construct integrality gap instances that meet the upper bound of p 2. Our gap instances can be viewed as a weighted graph sequence converging to a "graph limit structure".

AB - 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 2 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 inand 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 p 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 non-trivial distributions, and (2) we construct integrality gap instances that meet the upper bound of p 2. Our gap instances can be viewed as a weighted graph sequence converging to a "graph limit structure".

UR - http://www.scopus.com/inward/record.url?scp=85045564400&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045564400&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.92

DO - 10.1137/1.9781611975031.92

M3 - Conference contribution

AN - SCOPUS:85045564400

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1393

EP - 1406

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -