The Library
Parameterized approximation algorithms for bidirected Steiner network problems
Tools
Tools
Tools
Chitnis, Rajesh, Feldmann, Andreas Emil and Manurangsi, Pasin (2018) Parameterized approximation algorithms for bidirected Steiner network problems. In: 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland, 20–22 Aug 2018. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 112 20:1-20:16. ISBN 9783959770811. doi:10.4230/LIPIcs.ESA.2018.20 ISSN 1868-8969.
|
PDF
WRAP-parameterized-approximation-algorithms-bidirected-steiner-network-problems-Chitnis-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (533Kb) | Preview |
|
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
dcs-011118-wrap--main.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (1130Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.ESA.2018.20
Abstract
The Directed Steiner Network (DSN) problem takes as input a directed edge-weighted 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/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-DSN_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 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-DSN_Planar, unless FPT=W[1]. Additionally we study several generalizations of bi-DSN_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 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-{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 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.
| Item Type: | Conference Item (Paper) | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
| Library of Congress Subject Headings (LCSH): | Steiner systems, Approximation theory, Parameter estimation, Computer algorithms, Computer science -- Mathematics | |||||||||||||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||||||||
| ISBN: | 9783959770811 | |||||||||||||||
| ISSN: | 1868-8969 | |||||||||||||||
| Official Date: | 2018 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Volume: | 112 | |||||||||||||||
| Page Range: | 20:1-20:16 | |||||||||||||||
| DOI: | 10.4230/LIPIcs.ESA.2018.20 | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
| Date of first compliant deposit: | 2 November 2018 | |||||||||||||||
| Date of first compliant Open Access: | 5 November 2018 | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||
| Title of Event: | 26th Annual European Symposium on Algorithms (ESA 2018) | |||||||||||||||
| Type of Event: | Conference | |||||||||||||||
| Location of Event: | Helsinki, Finland | |||||||||||||||
| Date(s) of Event: | 20–22 Aug 2018 | |||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
