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/

Zendy Pro

Presents the zaia usage as premium feature

ZAIA

Presents AI Discovery search usage as a premium feature

AI Discovery

Presents AI Discovery explain and summary usage as a premium feature

Content Analysis

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Presents the pdf analysis as premium feature

PDF Analysis

1500 Top-up

3000 Top-up

Zendy Basic

2500 Top-up

Zendy Unlimited

Presents the access of premium content as premium feature

Premium Content

In the Directed Disjoint Paths problem, we are given a digraph $D$ and a setof requests $\{(s_1, t_1), \ldots, (s_k, t_k)\}$, and the task is to find acollection of pairwise vertex-disjoint paths $\{P_1, \ldots, P_k\}$ such thateach $P_i$ is a path from $s_i$ to $t_i$ in $D$. This problem is NP-completefor fixed $k=2$ and W[1]-hard with parameter $k$ in DAGs. A few positiveresults are known under restrictions on the input digraph, such as being planaror having bounded directed tree-width, or under relaxations of the problem,such as allowing for vertex congestion. Positive results are scarce, however,for general digraphs. In this article we propose a novel global congestionmetric for the problem: we only require the paths to be "disjoint enough", inthe sense that they must behave properly not in the whole graph, but in anunspecified part of size prescribed by a parameter. Namely, in the DisjointEnough Directed Paths problem, given an $n$-vertex digraph $D$, a set of $k$requests, and non-negative integers $d$ and $s$, the task is to find acollection of paths connecting the requests such that at least $d$ vertices of$D$ occur in at most $s$ paths of the collection. We study the parameterizedcomplexity of this problem for a number of choices of the parameter, includingthe directed tree-width of $D$. Among other results, we show that the problemis W[1]-hard in DAGs with parameter $d$ and, on the positive side, we give analgorithm in time $\mathcal{O}(n^{d+2} \cdot k^{d\cdot s})$ and a kernel ofsize $d \cdot 2^{k-s}\cdot \binom{k}{s} + 2k$ in general digraphs. This latterresult has consequences for the Steiner Network problem: we show that it is FPTparameterized by the number $k$ of terminals and $p$, where $p = n - q$ and $q$is the size of the solution.

A relaxation of the Directed Disjoint Paths problem: a global congestion metric helps