Chitnis, Rajesh ;
Feldmann, Andreas Emil ;
Manurangsi, Pasin
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Abstract
The Directed Steiner Network (DSN) problem takes as input a directed edgeweighted graph G=(V,E) and a set {D}subseteq V x V of k demand pairs. The aim is to compute the cheapest network N subseteq G for which there is an s > t path for each (s,t)in {D}. It is known that this problem is notoriously hard as there is no k^{1/4o(1)}approximation algorithm under GapETH, even when parameterizing the runtime by k [Dinur & Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter k.
For the biDSN_Planar problem, the aim is to compute a planar optimum solution N subseteq G in a bidirected graph G, i.e. for every edge uv of G the reverse edge vu exists and has the same weight. This problem is a generalization of several wellstudied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for k. We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) it is unlikely that a PAS exists for any generalization of biDSN_Planar, unless FPT=W[1]. Additionally we study several generalizations of biDSN_Planar and obtain upper and lower bounds on obtainable runtimes parameterized by k.
One important special case of DSN is the Strongly Connected Steiner Subgraph (SCSS) problem, for which the solution network N subseteq G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2approximation exists when parameterized by k [Chitnis et al., IPEC 2013]. We show a tight inapproximability result: under GapETH there is no (2{epsilon})approximation algorithm parameterized by k (for any epsilon>0). To the best of our knowledge, this is the first example of a W[1]hard problem admitting a nontrivial parameterized approximation factor which is also known to be tight! Additionally we show that when restricting the input of SCSS to bidirected graphs, the problem remains NPhard but becomes FPT for k.
BibTeX  Entry
@InProceedings{chitnis_et_al:LIPIcs:2018:9483,
author = {Rajesh Chitnis and Andreas Emil Feldmann and Pasin Manurangsi},
title = {{Parameterized Approximation Algorithms for Bidirected Steiner Network Problems}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {20:120:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9483},
URN = {urn:nbn:de:0030drops94833},
doi = {10.4230/LIPIcs.ESA.2018.20},
annote = {Keywords: Directed Steiner Network, Strongly Connected Steiner Subgraph, Parameterized Approximations, Bidirected Graphs, Planar Graphs}
}
2018
Keywords: 

Directed Steiner Network, Strongly Connected Steiner Subgraph, Parameterized Approximations, Bidirected Graphs, Planar Graphs 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 