Global and fixed-terminal cuts in digraphs

DOI10.4230/LIPICS.APPROX-RANDOM.2017.2MaRDI QIDQ5002602zbMATH OpenFDO

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

Publication date 28 July 2021

Full work available at URL https://arxiv.org/abs/1612.00156

zbMATH Keywords

directed graphshardness of approximationarborescencegraph cuts

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

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. 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$ under the Unique Games Conjecture (UGC). 2. The fixed-terminal edge-weighted bicut is known to have a tight approximability factor of $2$. 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. 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 enumeration of approximate min-cuts. Our hardness results are based on combinatorial reductions and integrality gap instances.

Recommendations

• Beating the 2-approximation factor for global bicut
• Hardness of cut problems in directed graphs
• The Complexity of Multiterminal Cuts
• Multicuts in unweighted digraphs with bounded degree and bounded tree-width
• New results on planar and directed multicuts

Cites work

• scientific article; zbMATH DE number 5485510 (Why is no real title available?)
• A 2-approximation algorithm for the directed multiway cut problem
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A new approach to the minimum cut problem
• An improved approximation algorithm of MULTIWAY CUT.
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• Approximating multicut and the demand graph
• Augmenting undirected node-connectivity by one
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of approximating bounded variants of optimization problems
• Computing minimum multiway cuts in hypergraphs
• Derandomization through approximation, an NC algorithm for minimum cuts
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
• Fault-tolerant consensus in directed graphs
• Finding minimum 3-way cuts in hypergraphs
• Gaussian bounds for noise correlation of functions
• Greedy splitting algorithms for approximating multiway partition problems
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Multiway cuts in node weighted graphs
• On shredders and vertex connectivity augmentation
• On the number of shredders
• Optimal 3-terminal cuts and linear programming
• Simple and fast rounding algorithms for directed and node-weighted multiway cut
• The Complexity of Multiterminal Cuts

Cited in

(2)

• Beating the 2-approximation factor for global bicut
• A tight \(\sqrt{2} \)-approximation for linear 3-cut

This page was built for publication: Global and fixed-terminal cuts in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002602)