Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments

Abstract

In the problem {\sc Min-DESC}, we are given a digraph $D$ and an integer $k$, and asked if there exists a set $A^{\prime }$ of at most $k$ arcs in $D$, such that if we remove the arcs of $A^{\prime }$, in the resulting digraph every strong component is Eulerian. {\sc Min-DESC} is NP-hard; Cechlárová and Schlotter (IPEC 2010) asked if the problem is fixed-parameter tractable when parameterized by $k$. We consider the subproblem of{\sc Min-DESC} when $D$ is a tournament. We show that this problem is fixed-parameter tractable with respect to $k$.