Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)

Research output: Contribution to journalArticlepeer-review

Standard

Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions). / Chitnis, Rajesh; Feldmann, Andreas Emil ; Hajiaghayi, MohammadTaghi; Marx, Dániel.

In: SIAM Journal on Computing, Vol. 49, No. 2, 25.03.2020, p. 318–364.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Chitnis, Rajesh ; Feldmann, Andreas Emil ; Hajiaghayi, MohammadTaghi ; Marx, Dániel. / Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions). In: SIAM Journal on Computing. 2020 ; Vol. 49, No. 2. pp. 318–364.

Bibtex

@article{8f056b96514c4dc5bcc2a3b905f03d28,
title = "Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)",
abstract = "Given a vertex-weighted directed graph G=(V,E) and a set T={t1 ,t2 ,…tk } of k terminals, the objective of the STRONGLY CONNECTED STEINER SUBGRAPH (SCSS) problem is to find a vertex set H⊆V of minimum weight such that G[H] contains a ti →tj path for each i≠j . The problem is NP-hard, but Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543--561] gave a novel nO(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a 2O(k)⋅nO(√k)   algorithm for planar SCSS, which is an improvement of a factor of O(√k)  in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f(k)⋅no(√k) algorithm for any computable function f , unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is of O(√k) , and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner NetworkProblems, preprint, https://arxiv.org/abs/1707.06808]. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our  2O(k)⋅nO(√k) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the nO(k) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k)⋅no(k/ log k) algorithm for any computable function f. Feldman and Ruhl generalized their nO(k) algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source si there is a path to the corresponding terminal ti. We show that, assuming ETH, there is no f(k)⋅no(k) time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.",
keywords = "strongly connected Steiner subgraph, FPT algorithms, directed Steiner network, exponential time hypothesis, planar graphs",
author = "Rajesh Chitnis and Feldmann, {Andreas Emil} and MohammadTaghi Hajiaghayi and D{\'a}niel Marx",
year = "2020",
month = mar,
day = "25",
doi = "10.1137/18M122371X",
language = "English",
volume = "49",
pages = "318–364",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics",
number = "2",

}

RIS

TY - JOUR

T1 - Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)

AU - Chitnis, Rajesh

AU - Feldmann, Andreas Emil

AU - Hajiaghayi, MohammadTaghi

AU - Marx, Dániel

PY - 2020/3/25

Y1 - 2020/3/25

N2 - Given a vertex-weighted directed graph G=(V,E) and a set T={t1 ,t2 ,…tk } of k terminals, the objective of the STRONGLY CONNECTED STEINER SUBGRAPH (SCSS) problem is to find a vertex set H⊆V of minimum weight such that G[H] contains a ti →tj path for each i≠j . The problem is NP-hard, but Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543--561] gave a novel nO(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a 2O(k)⋅nO(√k)   algorithm for planar SCSS, which is an improvement of a factor of O(√k)  in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f(k)⋅no(√k) algorithm for any computable function f , unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is of O(√k) , and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner NetworkProblems, preprint, https://arxiv.org/abs/1707.06808]. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our  2O(k)⋅nO(√k) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the nO(k) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k)⋅no(k/ log k) algorithm for any computable function f. Feldman and Ruhl generalized their nO(k) algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source si there is a path to the corresponding terminal ti. We show that, assuming ETH, there is no f(k)⋅no(k) time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.

AB - Given a vertex-weighted directed graph G=(V,E) and a set T={t1 ,t2 ,…tk } of k terminals, the objective of the STRONGLY CONNECTED STEINER SUBGRAPH (SCSS) problem is to find a vertex set H⊆V of minimum weight such that G[H] contains a ti →tj path for each i≠j . The problem is NP-hard, but Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543--561] gave a novel nO(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a 2O(k)⋅nO(√k)   algorithm for planar SCSS, which is an improvement of a factor of O(√k)  in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f(k)⋅no(√k) algorithm for any computable function f , unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is of O(√k) , and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner NetworkProblems, preprint, https://arxiv.org/abs/1707.06808]. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our  2O(k)⋅nO(√k) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the nO(k) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k)⋅no(k/ log k) algorithm for any computable function f. Feldman and Ruhl generalized their nO(k) algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source si there is a path to the corresponding terminal ti. We show that, assuming ETH, there is no f(k)⋅no(k) time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.

KW - strongly connected Steiner subgraph

KW - FPT algorithms

KW - directed Steiner network

KW - exponential time hypothesis

KW - planar graphs

UR - https://www.siam.org/publications/journals/siam-journal-on-computing-sicomp

U2 - 10.1137/18M122371X

DO - 10.1137/18M122371X

M3 - Article

VL - 49

SP - 318

EP - 364

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 2

ER -