Włodarczyk, Michał
Parameterized Inapproximability for Steiner Orientation by Gap Amplification
Abstract
In the kSteiner Orientation problem, we are given a mixed graph, that is, with both directed and undirected edges, and a set of k terminal pairs. The goal is to find an orientation of the undirected edges that maximizes the number of terminal pairs for which there is a path from the source to the sink. The problem is known to be W[1]hard when parameterized by k and hard to approximate up to some constant for FPT algorithms assuming GapETH. On the other hand, no approximation factor better than 𝒪(k) is known.
We show that kSteiner Orientation is unlikely to admit an approximation algorithm with any constant factor, even within FPT running time. To obtain this result, we construct a selfreduction via a hashingbased gap amplification technique, which turns out useful even outside of the FPT paradigm. Precisely, we rule out any approximation factor of the form (log k)^o(1) for FPT algorithms (assuming FPT ≠ W[1]) and (log n)^o(1) for purely polynomialtime algorithms (assuming that the class W[1] does not admit randomized FPT algorithms). This constitutes a novel inapproximability result for polynomialtime algorithms obtained via tools from the FPT theory. Moreover, we prove kSteiner Orientation to belong to W[1], which entails W[1]completeness of (log k)^o(1)approximation for kSteiner Orientation. This provides an example of a natural approximation task that is complete in a parameterized complexity class.
Finally, we apply our technique to the maximization version of directed multicut  Max (k,p)Directed Multicut  where we are given a directed graph, k terminals pairs, and a budget p. The goal is to maximize the number of separated terminal pairs by removing p edges. We present a simple proof that the problem admits no FPT approximation with factor 𝒪(k^(1/2  ε)) (assuming FPT ≠ W[1]) and no polynomialtime approximation with ratio 𝒪(E(G)^(1/2  ε)) (assuming NP ⊈ coRP).
BibTeX  Entry
@InProceedings{wodarczyk:LIPIcs:2020:12511,
author = {Michał Włodarczyk},
title = {{Parameterized Inapproximability for Steiner Orientation by Gap Amplification}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {104:1104:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12511},
URN = {urn:nbn:de:0030drops125110},
doi = {10.4230/LIPIcs.ICALP.2020.104},
annote = {Keywords: approximation algorithms, fixedparameter tractability, hardness of approximation, gap amplification}
}
29.06.2020
Keywords: 

approximation algorithms, fixedparameter tractability, hardness of approximation, gap amplification 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 