Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed
  Number of Terminals (and Extensions)   (see paper for full abstract)
  Given a vertex-weighted directed graph $G=(V,E)$ and a set $T=\{t_1, t_2,
\ldots t_k\}$ of $k$ terminals, the objective of the SCSS problem is to find a
vertex set $H\subseteq V$ of minimum weight such that $G[H]$ contains a
$t_{i}\rightarrow t_j$ path for each $i\neq j$. The problem is NP-hard, but
Feldman and Ruhl [FOCS '99; SICOMP '06] gave a novel $n^{O(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 $2^{O(k)}\cdot n^{O(\sqrt{k})}$ algorithm
for planar SCSS, which is an improvement of a factor of $O(\sqrt{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)\cdot n^{o(\sqrt{k})}$ algorithm
for any computable function $f$, unless the Exponential Time Hypothesis (ETH)
fails.
  The following additional results put our upper and lower bounds in context:
  - In general graphs, we cannot hope for such a dramatic improvement over the
$n^{O(k)}$ algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs
does not have an $f(k)\cdot n^{o(k/\log k)}$ algorithm for any computable
function $f$.
  - Feldman and Ruhl generalized their $n^{O(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 $s_i$ there is a path to the
corresponding terminal $t_i$. We show that, assuming ETH, there is no
$f(k)\cdot n^{o(k)}$ time algorithm for DSN on acyclic planar graphs.

20
The categories of this paper are: acc-phys
21
The categories of this paper are: adap-org
16
The categories of this paper are: stat
3
The categories of this paper are: physics
33
The categories of this paper are: plasm-ph
22
The categories of this paper are: chao-dyn
6
The categories of this paper are: astro-ph
10
The categories of this paper are: q-bio
25
The categories of this paper are: patt-sol
28
The categories of this paper are: alg-geom
18
The categories of this paper are: econ
17
The categories of this paper are: q-fin
13
The categories of this paper are: quant-ph
15
The categories of this paper are: nucl-ex
36
The categories of this paper are: cmp-lg
12
The categories of this paper are: nucl-th