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

In the $k$-connected directed Steiner tree problem ($k$-DST), we are given an$n$-vertex directed graph $G=(V,E)$ with edge costs, a connectivity requirement$k$, a root $r\in V$ and a set of terminals $T\subseteq V$. The goal is to finda minimum-cost subgraph $H\subseteq G$ that has $k$ internally disjoint pathsfrom the root vertex $r$ to every terminal $t\in T$.  In this paper, we show the approximation hardness of $k$-DST for variousparameters, which thus close some long-standing open problems.  - $\Omega\left(|T|/\log |T|\right)$-approximation hardness, which holds underthe standard assumption $\mathrm{NP}\neq \mathrm{ZPP}$. The inapproximabilityratio is tightened to $\Omega\left(|T|\right)$ under the Strongish PlantedClique Hypothesis [Manurangsi, Rubinstein and Schramm, ITCS 2021].  The latter hardness result matches the approximation ratio of $|T|$ obtainedby a trivial approximation algorithm, thus closing the long-standing openproblem.  - $\Omega\left(\sqrt{2}^k / k\right)$-approximation hardness for the generalcase of $k$-DST under the assumption $\mathrm{NP}\neq\mathrm{ZPP}$. This is thefirst hardness result known for survivable network design problems with aninapproximability ratio exponential in $k$.  - $\Omega\left((k/L)^{L/4}\right)$-approximation hardness for $k$-DST on$L$-layered graphs for $L\le O\left(\log n\right)$. This almost matches theapproximation ratio of $O(k^{L-1}\cdot L \cdot \log |T|)$ achieving in$O\left(n^L\right)$-time due to Laekhanukit [ICALP`16].

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity