English

Item

ITEM ACTIONSEXPORT

Released

Paper

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

MPS-Authors
/persons/resource/persons255161

Sharma,  Roohani
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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})}.