English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

(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 avertex 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, butFeldman and Ruhl [FOCS '99; SICOMP '06] gave a novel $n^{O(k)}$ algorithm forthe SCSS problem, where $n$ is the number of vertices in the graph and $k$ isthe number of terminals. We explore how much easier the problem becomes onplanar directed graphs:  - Our main algorithmic result is a $2^{O(k)}\cdot n^{O(\sqrt{k})}$ algorithmfor planar SCSS, which is an improvement of a factor of $O(\sqrt{k})$ in theexponent over the algorithm of Feldman and Ruhl.  - Our main hardness result is a matching lower bound for our algorithm: weshow that planar SCSS does not have an $f(k)\cdot n^{o(\sqrt{k})}$ algorithmfor 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 graphsdoes not have an $f(k)\cdot n^{o(k/\log k)}$ algorithm for any computablefunction $f$.  - Feldman and Ruhl generalized their $n^{O(k)}$ algorithm to the more generalDirected Steiner Network (DSN) problem; here the task is to find a subgraph ofminimum weight such that for every source $s_i$ there is a path to thecorresponding 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.

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)