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 this paper, we study the complexity of two types of digraph packingproblems: perfect out-forests problem and Steiner cycle packing problem.  For the perfect out-forest problem, we prove that it is NP-hard to decidewhether a given strong digraph contains a 1-perfect out-forest. However, whenrestricted to a semicomplete digraph $D$, the problem of deciding whether $D$contains an $i$-perfect out-forest becomes polynomial-time solvable, where$i\in \{0,1\}$. We also prove that it is NP-hard to find a 0-perfect out-forestof maximum size in a connected acyclic digraph, and it is NP-hard to find a1-perfect out-forest of maximum size in a connected digraph.  For the Steiner cycle packing problem, when both $k\geq 2, \ell\geq 1$ arefixed integers, we show that the problem of deciding whether there are at least$\ell$ internally disjoint directed $S$-Steiner cycles in an Eulerian digraph$D$ is NP-complete, where $S\subseteq V(D)$ and $|S|=k$. However, when weconsider the class of symmetric digraphs, the problem becomes polynomial-timesolvable. We also show that the problem of deciding whether there are at least$\ell$ arc-disjoint directed $S$-Steiner cycles in a given digraph $D$ isNP-complete, where $S\subseteq V(D)$ and $|S|=k$.

Perfect Out-forests and Steiner Cycle Packing in Digraphs