Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Parameterized Inapproximability for Steiner Orientation by Gap Amplification

Uproszczony widok
dc.abstract.enIn the k-Steiner 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 Gap-ETH. On the other hand, no approximation factor better than (k) is known. We show that k-Steiner Orientation is unlikely to admit an approximation algorithm with any constant factor, even within FPT running time. To obtain this result, we construct a self-reduction via a hashing-based 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 polynomial-time algorithms (assuming that the class W[1] does not admit randomized FPT algorithms). This constitutes a novel inapproximability result for polynomial-time algorithms obtained via tools from the FPT theory. Moreover, we prove k-Steiner Orientation to belong to W[1], which entails W[1]-completeness of (log k)^o(1)-approximation for k-Steiner 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 polynomial-time approximation with ratio (|E(G)|^(1/2 - ε)) (assuming NP ⊈ co-RP).
dc.affiliationUniwersytet Warszawski
dc.conference.countryNiemcy
dc.conference.datefinish2020-07-11
dc.conference.datestart2020-07-08
dc.conference.placeSaarbrücken
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2020
dc.conference.weblinkhttps://icalp2020.saarland-informatics-campus.de/
dc.contributor.authorWłodarczyk, Michał
dc.date.accessioned2024-01-25T16:13:14Z
dc.date.available2024-01-25T16:13:14Z
dc.date.issued2020
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.4230/LIPICS.ICALP.2020.104
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/115497
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2020/12511/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages104:1-19
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enapproximation algorithms
dc.subject.enfixed-parameter tractability
dc.subject.enhardness of approximation
dc.subject.engap amplification
dc.titleParameterized Inapproximability for Steiner Orientation by Gap Amplification
dc.typeJournalArticle
dspace.entity.typePublication