License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.2
URN: urn:nbn:de:0030-drops-75511
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7551/
Bérczi, Kristóf ;
Chandrasekaran, Karthekeyan ;
Király, Tamás ;
Lee, Euiwoong ;
Xu, Chao
Global and Fixed-Terminal Cuts in Digraphs
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.
BibTeX - Entry
@InProceedings{brczi_et_al:LIPIcs:2017:7551,
author = {Krist{\'o}f B{\'e}rczi and Karthekeyan Chandrasekaran and Tam{\'a}s Kir{\'a}ly and Euiwoong Lee and Chao Xu},
title = {{Global and Fixed-Terminal Cuts in Digraphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {2:1--2:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-044-6},
ISSN = {1868-8969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7551},
URN = {urn:nbn:de:0030-drops-75511},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.2},
annote = {Keywords: Directed Graphs, Arborescence, Graph Cuts, Hardness of Approximation}
}
|
Keywords: |
|
Directed Graphs, Arborescence, Graph Cuts, Hardness of Approximation |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
11.08.2017 |
