Résumé :

We define a new parameter for tournaments called degreewidth. The degreewidth of a tournament T denoted by Delta(T) corresponds to the minimum k such that we can order the vertices of T such that every vertex is incident to at most k backward arcs, i.e. for such arcs the head is before the tail w.r.t this order. Thus, a tournament is acyclic if and only if its degreewidth is zero. Additionally, the class of sparse tournaments defined by Bessy et al. corresponds to tournaments with degreewidth one. Therefore, this parameter can be seen as a measure of how far the tournament is from being acyclic. We first study computational complexity of finding degreewidth. Namely, we show it is NP-hard and complement this result by a 3-approximation algorithm. We also provide a cubic algorithm to decide if a tournament is sparse. Finally, we study classical graph problems Dominating Set and Feedback Vertex Set parameterized by degreewidth. We show the former is fixed parameter tractable whereas the later is NP-hard on tournaments of degreewidth one. Additionally, we study Feedback Arc Set on sparse tournaments.