Global and fixed-terminal cuts in digraphs

DOI10.4230/LIPICS.APPROX-RANDOM.2017.2zbMATH Open1467.68134arXiv1612.00156MaRDI QIDQ5002602FDOQ5002602

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

Publication date: 28 July 2021

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.

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

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

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)

Cites Work

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

Cited In (1)

• 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)