Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10437394" target="_blank" >RIV/00216208:11320/21:10437394 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=a.QxLFrQ_e" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=a.QxLFrQ_e</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3447584" target="_blank" >10.1145/3447584</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

Popis výsledku v původním jazyce

The Directed Steiner Network (DSN) problem takes as input a directed graph G = (V, E) with non-negative edge-weights and a set D subset of V x V of k demand pairs. The aim is to compute the cheapest network N subset of G for which there is an s -&gt; t path for each (s, t) is an element of 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 parametrizing the runtime by k [Dinur &amp; 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 solution N subset of G whose cost is at most that of an optimum planar solution 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) no PAS exists for any generalization of bi-DSNPLANAR, under standard complexity assumptions. The techniques we use also imply a polynomial-sized approximate kernelization scheme (PSAKS). 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 subset of G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists for parameter k [Chitnis et al., IPEC 2013]. We give a tight inapproximability result by showing that for k no parameterized (2 - epsilon)-approximation algorithm exists under Gap-ETH. Additionally, we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for k.

Název v anglickém jazyce

Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

Popis výsledku anglicky

The Directed Steiner Network (DSN) problem takes as input a directed graph G = (V, E) with non-negative edge-weights and a set D subset of V x V of k demand pairs. The aim is to compute the cheapest network N subset of G for which there is an s -&gt; t path for each (s, t) is an element of 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 parametrizing the runtime by k [Dinur &amp; 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 solution N subset of G whose cost is at most that of an optimum planar solution 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) no PAS exists for any generalization of bi-DSNPLANAR, under standard complexity assumptions. The techniques we use also imply a polynomial-sized approximate kernelization scheme (PSAKS). 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 subset of G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists for parameter k [Chitnis et al., IPEC 2013]. We give a tight inapproximability result by showing that for k no parameterized (2 - epsilon)-approximation algorithm exists under Gap-ETH. Additionally, we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for k.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACM Transactions on Algorithms

ISSN

1549-6325

e-ISSN

—

Svazek periodika

17

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

68

Strana od-do

12

Kód UT WoS článku

000661311300002

EID výsledku v databázi Scopus

2-s2.0-85107813086