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 Plus

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

Zendy Tools

Zendy Open

A directed odd cycle transversal of a directed graph (digraph) $D$ is avertex set $S$ that intersects every odd directed cycle of $D$. In the DirectedOdd Cycle Transversal (DOCT) problem, the input consists of a digraph $D$ andan integer $k$. The objective is to determine whether there exists a directedodd cycle transversal of $D$ of size at most $k$.  In this paper, we settle the parameterized complexity of DOCT whenparameterized by the solution size $k$ by showing that DOCT does not admit analgorithm with running time $f(k)n^{O(1)}$ unless FPT = W[1]. On the positiveside, we give a factor $2$ fixed parameter tractable (FPT) approximationalgorithm for the problem. More precisely, our algorithm takes as input $D$ and$k$, runs in time $2^{O(k^2)}n^{O(1)}$, and either concludes that $D$ does nothave a directed odd cycle transversal of size at most $k$, or produces asolution of size at most $2k$. Finally, we provide evidence that there exists$\epsilon > 0$ such that DOCT does not admit a factor $(1+\epsilon)$FPT-approximation algorithm.

Parameterized Complexity and Approximability of Directed Odd Cycle Transversal