Parameterized approximation algorithms for bidirected steiner network problems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • University of Warwick
  • Charles University, Prague
  • University of California, Berkeley

Abstract

The DIRECTED STEINER NETWORK (DSN) problem takes as input a directed edge-weighted graph G = (V, E) and a set D ⊆ V × V of k demand pairs. The aim is to compute the cheapest network N ⊆ G for which there is an s → t path for each (s,t) ∈ D. It is known that this problem is notoriously hard as there is no k1/4-o(1)-approximation algorithm under Gap-ETH, 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 BI-DSNPLANAR problem, the aim is to compute a planar optimum solution N ⊆ 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 well-studied 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 BI-DSNPLANAR, unless FPT=W[1]. Additionally we study several generalizations of BI-DSNPLANAR 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 ⊆ G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists when parameterized by k [Chitnis et al., IPEC 2013]. We show a tight inapproximability result: under Gap-ETH there is no (2 - ϵ)-approximation algorithm parameterized by k (for any ϵ > 0). To the best of our knowledge, this is the first example of a W[1]-hard problem admitting a non-trivial 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 NP-hard but becomes FPT for k.

Details

Original languageEnglish
Title of host publication26th European Symposium on Algorithms, (ESA 2018).
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
Publication statusPublished - 1 Aug 2018
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: 20 Aug 201822 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume112
ISSN (Print)1868-8969

Conference

Conference26th European Symposium on Algorithms, ESA 2018
CountryFinland
CityHelsinki
Period20/08/1822/08/18

Keywords

  • Bidirected graphs, Directed steiner network, Parameterized approximations, Planar graphs, Strongly connected steiner subgraph

ASJC Scopus subject areas