Résumé
In the paper, we define a new parameter for tournaments called degreewidth which can be seen as a measure of how far is the tournament from being acyclic. The degreewidth of a tournament T denoted by ∆(T) is the minimum value k for which we can find an ordering ⟨v1,. .. , vn⟩ of the vertices of T such that every vertex is incident to at most k backward arcs (i.e. an arc (vi, vj) such that j < i). Thus, a tournament is acyclic if and only if its degreewidth is zero. Additionally, the class of sparse tournaments defined by Bessy et al. [ESA 2017] is exactly the class of tournaments with degreewidth one. We study computational complexity of finding degreewidth. We show it is NP-hard and complement this result with a 3-approximation algorithm. We provide a O(n 3)-time algorithm to decide if a tournament is sparse, where n is its number of vertices. 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 latter is NP-hard even on sparse tournaments. Additionally, we show polynomial time algorithm for Feedback Arc Set on sparse tournaments.