Abstract
We study variants of the classic st cut problem and prove the following improved hardness results assuming the Unique Games Conjecture (UGC).
* For LengthBounded 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 ratio for LengthBounded Cut matches the best approximation ratio up to a constant. Previously, the best hardness ratio was 1.1377 for LengthBounded Cut and 2 for Shortest Path Interdiction.
* For any constant k >= 2 and epsilon > 0, we show that Directed Multicut with k sourcesink pairs is hard to approximate within a factor k  epsilon. This matches the trivial kapproximation algorithm. By a simple reduction, our result for k = 2 implies that Directed Multiway Cut with two terminals (also known as st Bicut} is hard to approximate within a factor 2  epsilon, matching the trivial 2approximation algorithm.
* 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 ratio was 2. For directed layered graphs with b layers, our hardness ratio Omega(log b) matches the best approximation algorithm.
Our results are based on a general method of converting an integrality gap instance to a lengthcontrol dictatorship test for variants of the st cut problem, which may be useful for other problems.
BibTeX  Entry
@InProceedings{lee:LIPIcs:2017:7485,
author = {Euiwoong Lee},
title = {{Improved Hardness for Cut, Interdiction, and Firefighter Problems}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {92:192:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7485},
URN = {urn:nbn:de:0030drops74854},
doi = {10.4230/LIPIcs.ICALP.2017.92},
annote = {Keywords: length bounded cut, shortest path interdiction, multicut; firefighter, unique games conjecture}
}
Keywords: 

length bounded cut, shortest path interdiction, multicut; firefighter, unique games conjecture 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) 
Issue Date: 

2017 
Date of publication: 

06.07.2017 