Global and fixed-terminal cuts in digraphs

K Bérczi, K Chandrasekaran, T Király, E Lee… - arXiv preprint arXiv …, 2016 - arxiv.org
arXiv preprint arXiv:1612.00156, 2016arxiv.org
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. The
fixed-terminal edge-weighted double cut is known to be solvable efficiently. We show a tight
approximability factor of $2 $ for the fixed-terminal node-weighted double cut. We show that
the global node-weighted double cut cannot be approximated to a factor smaller than $3/2 …
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. The fixed-terminal edge-weighted double cut is known to be solvable efficiently. We show a tight approximability factor of for the fixed-terminal node-weighted double cut. We show that the global node-weighted double cut cannot be approximated to a factor smaller than under the Unique Games Conjecture (UGC). 2. The fixed-terminal edge-weighted bicut is known to have a tight approximability factor of . We show that the global edge-weighted bicut is approximable to a factor strictly better than , and that the global node-weighted bicut cannot be approximated to a factor smaller than 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 for the node-weighted -cut problem. Second, we show that for constant , there exists an efficient algorithm to solve the minimum -separating -cut problem. Our techniques for the algorithms are combinatorial, based on LPs and based on enumeration of approximate min-cuts. Our hardness results are based on combinatorial reductions and integrality gap instances.
arxiv.org
以上显示的是最相近的搜索结果。 查看全部搜索结果