TY - GEN
T1 - Global and fixed-terminal cuts in digraphs
AU - Bérczi, Kristóf
AU - Chandrasekaran, Karthekeyan
AU - Király, Tamás
AU - Lee, Euiwoong
AU - Xu, Chao
N1 - ∗ A full version of the paper is available at https://arxiv.org/abs/1612.00156. † Kristóf and Tamás are supported by the Hungarian National Research, Development and Innovation Office – NKFIH grants K109240 and K120254. Chao is supported in part by NSF grant CCF-1526799.
PY - 2017/8/1
Y1 - 2017/8/1
N2 - 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.
AB - 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.
KW - Directed Graphs, Arborescence, Graph Cuts, Hardness of Approximation
UR - http://www.scopus.com/inward/record.url?scp=85028691483&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028691483&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX/RANDOM.2017.2
DO - 10.4230/LIPIcs.APPROX/RANDOM.2017.2
M3 - Conference contribution
AN - SCOPUS:85028691483
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017
A2 - Rolim, Jose D. P.
A2 - Jansen, Klaus
A2 - Williamson, David P.
A2 - Vempala, Santosh S.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2017 and the 21st International Workshop on Randomization and Computation, RANDOM 2017
Y2 - 16 August 2017 through 18 August 2017
ER -