Improved hardness for cut, interdiction, and firefighter problems

DOI10.4230/LIPICS.ICALP.2017.92zbMATH Open1442.68067arXiv1607.05133OpenAlexW2963724423MaRDI QIDQ5111424FDOQ5111424

Authors: Euiwoong Lee 

Publication date: 27 May 2020

Abstract: We study variants of the classic $s$-$t$ cut problem and prove the following improved hardness results assuming the Unique Games Conjecture (UGC). - For any constant $kgeq2$ and $epsilon>0$, we show that Directed Multicut with $k$ source-sink pairs is hard to approximate within a factor $k-epsilon$. This matches the trivial $k$-approximation algorithm. By a simple reduction, our result for $k=2$ implies that Directed Multiway Cut with two terminals (also known as $s$-$t$ Bicut) is hard to approximate within a factor $2-epsilon$, matching the trivial $2$-approximation algorithm. Previously, the best hardness factor for these problems (for constant $k$) was $1.5-epsilon$ under the UGC. - For Length-Bounded Cut and Shortest Path Interdiction, we show that both problems are hard to approximate within any constant factor, even if we allow bicriteria approximation. If we want to cut vertices or the graph is directed, our hardness factor for Length-Bounded Cut matches the best approximation ratio up to a constant. Previously, the best hardness factor was $1.1377$ for Length-Bounded Cut and $2$ for Shortest Path Interdiction. - Assuming a variant of the UGC (implied by another variant of Bansal and Khot), we prove that it is hard to approximate Resource Minimization Fire Containment within any constant factor. Previously, the best hardness factor was $2$. Our results are based on a general method of converting an integrality gap instance to a length-control dictatorship test for variants of the $s$-$t$ cut problem, which may be useful for other problems.

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

Recommendations

• On the hardness of approximating Multicut and Sparsest-Cut
• Hardness of cut problems in directed graphs
• Hardness and approximation for network flow interdiction
• Polynomial flow-cut gaps and hardness of directed cut problems
• Length-Bounded Cuts and Flows

zbMATH Keywords

unique games conjecturemulticutfirefighterlength-bounded cutshortest path interdiction

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (9)

• On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow
• The Quest for Strong Inapproximability Results with Perfect Completeness
• Minimum Violation Vertex Maps and Their Applications to Cut Problems
• Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment
• Title not available (Why is that?)
• Beating the 2-approximation factor for global bicut
• Fitting metrics and ultrametrics with minimum disagreements
• On Algorithms Employing Treewidth for $L$-bounded Cut Problems
• A tight \(\sqrt{2} \)-approximation for linear 3-cut

This page was built for publication: Improved hardness for cut, interdiction, and firefighter problems

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