Approximating multicut and the demand graph

DOI10.1137/1.9781611974782.54MaRDI QIDQ4575793zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Vivek Madan

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Abstract: In the minimum Multicut problem, the input is an edge-weighted supply graph $G=(V,E)$ and a simple demand graph $H=(V,F)$. Either $G$ and $H$ are directed (DMulC) or both are undirected (UMulC). The goal is to remove a minimum weight set of edges in $G$ such that there is no path from $s$ to $t$ in the remaining graph for any $(s,t)inF$. UMulC admits an $O(logk)$-approximation where $k$ is the vertex cover size of $H$ while the best known approximation for DMulC is $mink,ildeO(n^{11/23})$. These approximations are obtained by proving corresponding results on the multicommodity flow-cut gap. In contrast to these results some special cases of Multicut, such as the well-studied Multiway Cut problem, admit a constant factor approximation in both undirected and directed graphs. Motivated by both concrete instances from applications and abstract considerations, we consider the role that the structure of the demand graph $H$ plays in determining the approximability of Multicut. In undirected graphs our main result is a $2$-approximation in $n^{O(t)}$ time when the demand graph $H$ excludes an induced matching of size $t$. This gives a constant factor approximation for a specific demand graph that motivated this work. In contrast to undirected graphs, we prove that in directed graphs such approximation algorithms can not exist. Assuming the Unique Games Conjecture (UGC), for a large class of fixed demand graphs DMulC cannot be approximated to a factor better than worst-case flow-cut gap. As a consequence we prove that for any fixed $k$, assuming UGC, DMulC with $k$ demand pairs is hard to approximate to within a factor better than $k$. On the positive side, we prove an approximation of $k$ when the demand graph excludes certain graphs as an induced subgraph. This generalizes the Multiway Cut result to a much larger class of demand graphs.

Recommendations

• Approximation and Online Algorithms
• Hardness of cut problems in directed graphs
• Greedy approximation algorithms for directed multicuts
• scientific article; zbMATH DE number 2079369
• Approximation Algorithms for Steiner and Directed Multicuts

Cited in

(9)

• A tight \(\sqrt{2} \)-approximation for linear 3-cut
• Beating the 2-approximation factor for global bicut
• On the hardness of approximating Multicut and Sparsest-Cut
• Hardness of cut problems in directed graphs
• scientific article; zbMATH DE number 1342136 (Why is no real title available?)
• Global and fixed-terminal cuts in digraphs
• Minimum violation vertex maps and their applications to cut problems
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Approximation algorithms for requirement cut on graphs

This page was built for publication: Approximating multicut and the demand graph

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