TY - JOUR
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:
© 2019, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
PY - 2020/11/1
Y1 - 2020/11/1
N2 - We investigate the approximability of the linear 3-cut problem in directed graphs. 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 precise 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 2-approximation algorithm and show that this factor is tight under 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 2. Our gap instances can be viewed as a weighted graph sequence converging to a “graph limit structure”. We complement our results by showing connections between the linear 3-cut problem and other fundamental cut problems in directed graphs.
AB - We investigate the approximability of the linear 3-cut problem in directed graphs. 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 precise 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 2-approximation algorithm and show that this factor is tight under 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 2. Our gap instances can be viewed as a weighted graph sequence converging to a “graph limit structure”. We complement our results by showing connections between the linear 3-cut problem and other fundamental cut problems in directed graphs.
KW - Approximation
KW - Directed multicut
KW - Linear cut
KW - Multicut
UR - http://www.scopus.com/inward/record.url?scp=85069839417&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069839417&partnerID=8YFLogxK
U2 - 10.1007/s10107-019-01417-9
DO - 10.1007/s10107-019-01417-9
M3 - Article
AN - SCOPUS:85069839417
SN - 0025-5610
VL - 184
SP - 411
EP - 443
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -