2026-07-26T02:32:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7551 2024-03-06T10:40:35Z ddc:004 open_access

Global and Fixed-Terminal Cuts in Digraphs Bérczi, Kristóf Chandrasekaran, Karthekeyan Király, Tamás Lee, Euiwoong Xu, Chao Directed Graphs Arborescence Graph Cuts Hardness of Approximation 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. Fixed-terminal edge-weighted double cut is known to be solvable efficiently. We show that fixed-terminal node-weighted double cut cannot be approximated to a factor smaller than 2 under the Unique Games Conjecture (UGC), and we also give a 2-approximation algorithm. For the global version of the problem, we prove an inapproximability bound of 3/2 under UGC. 2. Fixed-terminal edge-weighted bicut is known to have an approximability factor of 2 that is tight under UGC. 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 under UGC. 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 the enumeration of approximate min-cuts. Our hardness results are based on combinatorial reductions and integrality gap instances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kristóf Bérczi and Karthekeyan Chandrasekaran and Tamás Király and Euiwoong Lee and Chao Xu 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.2 urn:nbn:de:0030-drops-75511 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.2 eng https://creativecommons.org/licenses/by/3.0/legalcode