A tight $$\sqrt{2}$$ 2 -approximation for linear 3-cut
- PDF / 2,617,807 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 229 Views
Series A
A tight
√
2-approximation for linear 3-cut
Kristóf Bérczi1 · Karthekeyan Chandrasekaran2 · Tamás Király1 · Vivek Madan2 Received: 2 February 2018 / Accepted: 23 July 2019 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2019
Abstract 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 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. Keywords Linear cut · Multicut · Directed multicut · Approximation Mathematics Subject Classification 90C27 · 68Q25 · 68W25 · 05C20 · 05C85
An extended abstract of this work appeared in the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018). Kristóf and Tamás are supported by the Hungarian National Research, Development and Innovation Office—NKFIH Grants K109240 and K120254 and by the ÚNKP-17-4 New National Excellence Program of the Ministry of Human Capacities. Karthekeyan is supported by NSF CCF-1907937 and NSF CCF-1814613. Vivek is supported by NSF CCF-1319376. Electronic supplementary material The online version of this article (https://doi.org/10.1007/s10107019-01417-9) contains supplementary material, which is available to authorized users.
B
Karthekeyan Chandrasekaran [email protected]
Extended author information available on the last page of the article
123
K. Bérczi et al.
1 Introduction We investigate the approximability of the linear 3-cut problem in directed graphs. We formally distinguish the node weighted and edge weighted variants below: (s, r , t)-Node-Lin-3-Cut: The input is a directed graph D = (V , E) with specified V \{r ,s,t} nodes s, r , t ∈ V and node weights w ∈ R+ , and the goal is to find a minimum weight node set U ⊆ V \{r , s, t} such that D[V − U ] has no path from s to t, from s to r and from r to t. (s, r , t) -Edge-Lin-3-Cut: The input is a directed graph D = (V , E) with specified E , and the goal is to find a minimum weight nodes s, r , t ∈ V and edge weights w ∈ R+ edge set F ⊆ E such that D − F has
Data Loading...
