2016/12/01 by Kristóf Bérczi, Bérczi, Kristóf, Karthekeyan Chandrasekaran +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DS #math.OC
paper · pdf · doi:10.48550/arxiv.1612.00156
37 pages, 5 figures, APPROX 2017
openalex publication_date 2016/12/01 · arxiv created 2017/07/06 · arxiv updated 2017/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The computational complexity of multicut-like problems may vary significantly depending on whether the terminals are fixed or not. In this work we present a comprehensive study of this phenomenon in two types of cut problems in directed graphs: double cut and bicut. 1. The fixed-terminal edge-weighted double cut is known to be solvable efficiently. We show a tight approximability factor of 2 for the fixed-terminal node-weighted double cut. We show that the global node-weighted double cut cannot be approximated to a factor smaller than 3/2 under the Unique Games Conjecture (UGC). 2. The fixed-terminal edge-weighted bicut is known to have a tight approximability factor of 2. We show that the global edge-weighted bicut is approximable to a factor strictly better than 2, and that the global node-weighted bicut cannot be approximated to a factor smaller than 3/2 under UGC. 3. In relation to these investigations, we also prove two results on undirected graphs which are of independent interest. First, we show NP-completeness and a tight inapproximability bound of 4/3 for the node-weighted 3-cut problem. Second, we show that for constant k, there exists an efficient algorithm to solve the minimum \s,t\-separating k-cut problem. Our techniques for the algorithms are combinatorial, based on LPs and based on enumeration of approximate min-cuts. Our hardness results are based on combinatorial reductions and integrality gap instances.