In the problem Min-DESC, we are given a digraph D and an integer k, and asked whether there exists a set A^' of at most k arcs in D, such that if we remove the arcs of A^', in the resulting digraph every strong component is Eulerian. Min-DESC is NP-hard; Cechlarova and Schlotter (IPEC 2010) asked whether the problem is fixed-parameter tractable when parameterized by k. We consider the subproblem of Min-DESC when D is a tournament. We show that this problem is fixed-parameter tractable with respect to k.
['Robert Crowston', 'Gregory Gutin', 'Mark Jones', 'Anders Yeo']
Parameterized Eulerian strong component arc deletion problem on tournaments