Odd Cycle Transversal in Mixed Graphs

An odd cycle transversal (oct, for short) in a graph is a set of vertices whose deletion will leave a graph without any odd cycles. The Odd Cycle Transversal (OCT) problem takes an undirected graph G and a non-negative integer k as input, and the objective is to test if G has an oct of size at most k. The directed counterpart of the problem, Directed Odd Cycle Transversal (DOCT), where the input is a digraph and k, is defined analogously. When parameterized by k, OCT is known to be FPT [Reed et al., Oper. Res. Lett., 2004] whereas DOCT was recently shown to be W[1]-hard [Lokshtanov et al., SODA, 2020].