# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2208.06015.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Galby, E., Kisfaludi-Bak, S., Marx, D., & Sharma, R. (2022). Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification. Retrieved from https://arxiv.org/abs/2208.06015.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1E72-3

##### Abstract

In the Directed Steiner Network problem, the input is a directed graph G, a

subset T of k vertices of G called the terminals, and a demand graph D on T.

The task is to find a subgraph H of G with the minimum number of edges such

that for every edge (s,t) in D, the solution H contains a directed s to t path.

In this paper we investigate how the complexity of the problem depends on the

demand pattern when G is planar. Formally, if \mathcal{D} is a class of

directed graphs closed under identification of vertices, then the

\mathcal{D}-Steiner Network (\mathcal{D}-SN) problem is the special case where

the demand graph D is restricted to be from \mathcal{D}. For general graphs,

Feldmann and Marx [ICALP 2016] characterized those families of demand graphs

where the problem is fixed-parameter tractable (FPT) parameterized by the

number k of terminals. They showed that if \mathcal{D} is a superset of one of

the five hard families, then \mathcal{D}-SN is W[1]-hard parameterized by k,

otherwise it can be solved in time f(k)n^{O(1)}.

For planar graphs an interesting question is whether the W[1]-hard cases can

be solved by subexponential parameterized algorithms. Chitnis et al. [SICOMP

2020] showed that, assuming the ETH, there is no f(k)n^{o(k)} time algorithm

for the general \mathcal{D}-SN problem on planar graphs, but the special case

called Strongly Connected Steiner Subgraph can be solved in time f(k)

n^{O(\sqrt{k})} on planar graphs. We present a far-reaching generalization and

unification of these two results: we give a complete characterization of the

behavior of every $\mathcal{D}$-SN problem on planar graphs. We show that

assuming ETH, either the problem is (1) solvable in time 2^{O(k)}n^{O(1)}, and

not in time 2^{o(k)}n^{O(1)}, or (2) solvable in time f(k)n^{O(\sqrt{k})}, but

not in time f(k)n^{o(\sqrt{k})}, or (3) solvable in time f(k)n^{O(k)}, but not

in time f(k)n^{o({k})}.

subset T of k vertices of G called the terminals, and a demand graph D on T.

The task is to find a subgraph H of G with the minimum number of edges such

that for every edge (s,t) in D, the solution H contains a directed s to t path.

In this paper we investigate how the complexity of the problem depends on the

demand pattern when G is planar. Formally, if \mathcal{D} is a class of

directed graphs closed under identification of vertices, then the

\mathcal{D}-Steiner Network (\mathcal{D}-SN) problem is the special case where

the demand graph D is restricted to be from \mathcal{D}. For general graphs,

Feldmann and Marx [ICALP 2016] characterized those families of demand graphs

where the problem is fixed-parameter tractable (FPT) parameterized by the

number k of terminals. They showed that if \mathcal{D} is a superset of one of

the five hard families, then \mathcal{D}-SN is W[1]-hard parameterized by k,

otherwise it can be solved in time f(k)n^{O(1)}.

For planar graphs an interesting question is whether the W[1]-hard cases can

be solved by subexponential parameterized algorithms. Chitnis et al. [SICOMP

2020] showed that, assuming the ETH, there is no f(k)n^{o(k)} time algorithm

for the general \mathcal{D}-SN problem on planar graphs, but the special case

called Strongly Connected Steiner Subgraph can be solved in time f(k)

n^{O(\sqrt{k})} on planar graphs. We present a far-reaching generalization and

unification of these two results: we give a complete characterization of the

behavior of every $\mathcal{D}$-SN problem on planar graphs. We show that

assuming ETH, either the problem is (1) solvable in time 2^{O(k)}n^{O(1)}, and

not in time 2^{o(k)}n^{O(1)}, or (2) solvable in time f(k)n^{O(\sqrt{k})}, but

not in time f(k)n^{o(\sqrt{k})}, or (3) solvable in time f(k)n^{O(k)}, but not

in time f(k)n^{o({k})}.