A tight2-approximation for linear 3-cut

• 成果类型: Article
• 署名作者: Berczi, Kristof; Chandrasekaran, Karthekeyan; Kiraly, Tamas; Madan, Vivek
• 署名单位: Eotvos Lorand University; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01417-9
• 发表日期: 2020
• 页码: 411-443
• 关键词: algorithms; cuts

摘要

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 nonterminal 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 v 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 v 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.