Global and fixed-terminal cuts in digraphs

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017
EditorsJose D. P. Rolim, Klaus Jansen, David P. Williamson, Santosh S. Vempala
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770446
DOIs
StatePublished - Aug 1 2017
Event20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2017 and the 21st International Workshop on Randomization and Computation, RANDOM 2017 - Berkeley, United States
Duration: Aug 16 2017Aug 18 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume81
ISSN (Print)1868-8969

Other

Other20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2017 and the 21st International Workshop on Randomization and Computation, RANDOM 2017
CountryUnited States
CityBerkeley
Period8/16/178/18/17

Keywords

  • Directed Graphs, Arborescence, Graph Cuts, Hardness of Approximation

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Global and fixed-terminal cuts in digraphs'. Together they form a unique fingerprint.

  • Cite this

    Bérczi, K., Chandrasekaran, K., Király, T., Lee, E., & Xu, C. (2017). Global and fixed-terminal cuts in digraphs. In J. D. P. Rolim, K. Jansen, D. P. Williamson, & S. S. Vempala (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017 [2] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 81). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2017.2