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

Given a directed graph $D$ on $n$ vertices and a positive integer $k$, theArc-Disjoint Cycle Packing problem is to determine whether $D$ has $k$arc-disjoint cycles. This problem is known to be W[1]-hard in general directedgraphs. In this paper, we initiate a systematic study on the parameterizedcomplexity of the problem restricted to tournaments. We show that the problemis fixed-parameter tractable and admits a polynomial kernel when parameterizedby the solution size $k$. In particular, we show that it can be solved in$2^{\mathcal{O}(k \log k)} n^{\mathcal{O}(1)}$ time and has a kernel with$\mathcal{O}(k)$ vertices. The primary ingredient in both these results is amin-max theorem that states that every tournament either contains $k$arc-disjoint triangles or has a feedback arc set of size at most $6k$. Ourbelief is that this combinatorial result is of independent interest and couldbe useful in other problems related to cycles in tournaments.

The Parameterized Complexity of Packing Arc-Disjoint Cycles in Tournaments