文章基本信息

标题：Global and Fixed-Terminal Cuts in Digraphs
本地全文：下载
作者：Krist{\'o}f B{\'e}rczi ; Karthekeyan Chandrasekaran ; Tam{\'a}s Kir{\'a}ly 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：2:1-2:20
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Directed Graphs; Arborescence; Graph Cuts; Hardness of Approximation