Tom Davot
email: tom.davot@hds.utc.fr

Lucas Isenmann
email: lucas.isenmann@umontpellier.fr

Sanjukta Roy
email: sanjukta@psu.edu

Jocelyn Thiebaut
email: jocelyn.thiebaut@cvut.cz

Degreewidth: a New Parameter for Solving Problems on Tournaments ⋆

Keywords: Tournaments, NP-hardness, graph-parameter, feedback arc set, approximation algorithm, parameterized algorithms

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.

Introduction

A tournament is a directed graph such that there is exactly one arc between each pair of vertices. Tournaments form a very rich subclass of digraphs which has been widely studied both from structural and algorithmic point of view [START_REF] Bang-Jensen | Digraphs -Theory, Algorithms and Applications[END_REF]. Unlike for complete graphs, a number of classical problems remain difficult in tournaments and therefore interesting to study. These problems include Dominating Set [START_REF] Downey | Parameterized computational feasibility[END_REF], Winner Determination [START_REF] Laslier | Tournament solutions and majority voting[END_REF], or maximum cycle packing problems. For example, Dominating Set is W [START_REF] Allesina | A competitive network theory of species diversity[END_REF]-hard on tournaments with respect to solution size [START_REF] Downey | Parameterized computational feasibility[END_REF]. However, many of these problems become easy on acyclic tournaments (i.e. without directed cycle). Therefore, a natural question that arises is whether these problems are easy to solve on tournaments that are close to being acyclic. The phenomenon of a tournament being "close to acyclic" can be captured by minimum size of a feedback arc set (fas). A fas is a collection of arcs that, when removed from the digraph (or, equivalently, reversed) makes it acyclic. This parameter has been widely studied, for numerous applications in many fields, such as circuit design [START_REF] Johnson | Finding all the elementary circuits of a directed graph[END_REF], or artificial intelligence [START_REF] Bar-Yehuda | Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference[END_REF][START_REF] Dechter | Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition[END_REF]. However, the problem of finding a minimum fas on tournaments (the problem is then called FAST for Feedback Arc Set in Tournaments), remained opened for over a decade before being proven NP-complete [START_REF] Alon | Ranking tournaments[END_REF][START_REF] Charbit | The minimum feedback arc set problem is np-hard for tournaments[END_REF]. From the approximability point of view, van Zuylen and Williamson [START_REF] Van Zuylen | Deterministic pivoting algorithms for constrained ranking and clustering problems[END_REF] provided a 2-approximation of FAST, and Kenyon-Mathieu and Schudy [START_REF] Kenyon-Mathieu | How to rank with few errors[END_REF] a PTAS algorithm. On the parameterizedcomplexity side, Feige [START_REF] Feige | Faster fast(feedback arc set in tournaments)[END_REF] as well as Karpinski and Schudy [START_REF] Karpinski | Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament[END_REF] independently proved an 2 O( √ k) + n O (1) running-time algorithm. Another way to define FAST is to consider the problem of finding an ordering of the vertices ⟨v 1 , . . . , v n ⟩ minimising the number of arcs (v i , v j ) with j < i; such arcs are called backward arcs. Then, it is easy to see that a tournament is acyclic if and only if it admits an ordering with no backward arcs. Several parameters exploiting an ordering with specific properties have been studied in this sense [START_REF] Gurski | Comparing linear width parameters for directed graphs[END_REF] such as the cutwidth. Given an ordering of vertices, for each prefix of the ordering we associate a cut defined as the set of backward arcs with head in the prefix and tail outside of it. Then cutwidth is the minimum value, among all the orderings, of the maximum size of any possible cut w.r.t the ordering (a formal definition is introduced in next section). It is well-known that computing cutwidth is NP-complete [START_REF] Gavril | some np-complete problems on graphs[END_REF], and has an O(log 2 (n))-approximation on general graphs [START_REF] Leighton | Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms[END_REF]. Specifically on tournaments, one can compute an optimal ordering for the cutwidth by sorting the degrees according to the in-degrees [START_REF] Fradkin | Forbidden Structures and Algorithms in Graphs and Digraphs[END_REF].

In this paper, we propose a new parameter called degreewidth using the concept of backward arcs in an ordering of vertices. Degreewidth of a tournament is the minimum value, among all the orderings, of the maximum number of backward arcs incident to a vertex. Hence, an acyclic tournament is a tournament with degreewidth zero. Furthermore, one can notice that tournaments with degreewidth at most one are the same as the sparse tournaments introduced in [8,[START_REF] Thiebaut | Algorithmic and structural results on directed cycles in dense digraphs[END_REF]. A tournament is sparse if there exists an ordering of vertices such that the backward arcs form a matching. It is known that computing a maximum sized arc-disjoint packing of triangles and computing a maximum sized arc-disjoint packing of cycles can be done in polynomial time [START_REF] Bessy | Packing arc-disjoint cycles in tournaments[END_REF] on sparse tournaments.

To the best of our knowledge this paper is the first to study the parameter degreewidth. As we will see in the next part, although having similarities with the cutwidth, this new parameter differs in certain aspects. We first study structural and computational aspects of degreewidth. Then, we show how it can be used to solve efficiently some classical problems on tournaments. Our contributions and organization of the paper Next section provides the formal definition of degreewidth and some preliminary observations. In Section 3, we first study the degreewidth of a special class of tournaments, called regular tournaments, of order 2k + 1 and prove they have degreewidth k. We then prove that it is NP-hard to compute the degreewidth in general tournaments. We finally give a 3-approximation algorithm to compute this parameter which is tight in the sense that it cannot produce better than 3-approximation for a class of tournaments.

Then in Section 4, we focus on tournaments with degreewidth one, i.e., the sparse tournaments. Note that it is claimed in [8] that there exists a polynomialtime algorithm for finding such ordering, but the only available algorithm appearing in [START_REF] Thiebaut | Algorithmic and structural results on directed cycles in dense digraphs[END_REF]Lemma 35.1,p.97] seems to be incomplete (see discussion Subsection 4.2). We first define a special class of tournaments that we call Utournaments. We prove there are only two possible sparse orderings for such tournaments. Then, we give a polynomial time algorithm to decide if a tournament is sparse by carefully decomposing it into U -tournaments.

Finally, in Section 5 we study degreewidth as a parameter for some classical graph problems. First, we show an FPT algorithm for Dominating Set w.r.t degreewidth. Then, we focus on tournaments with degreewidth one. We design an algorithm running in time O(n 3 ) to compute a Feedback Arc Set on tournaments on n vertices with degreewidth one. However, we show that Feedback Vertex Set remains NP-complete on this class of tournaments. Due to paucity of space the missing proofs are deferred to full version [START_REF] Davot | Degreewidth: a new parameter for solving problems on tournaments[END_REF].

Preliminaries

Notations

In the following, all the digraphs are simple, that is without self-loop and multiple arcs sharing the same head and tail, and all cycles are directed cycles. The underlying graph of a digraph D is an undirected graph obtained by replacing every arc of D by an edge. Furthermore, we use [n] to denote the set {1, 2, . . . , n}.

A tournament is a digraph where there is exactly one arc between each pair of vertices. It can alternatively be seen as an orientation of the complete graph. Let T be a tournament with vertex set {v 1 , . . . , v n }. We denote N + (v) the outneighbourhood of a vertex v, that is the set {u | (v, u) ∈ A(T )}. Then, T being a tournament, the in-neighbourhood of the vertex v denoted N -(v) corresponds to V (T ) \ (N + (v) ∪ {v}). The out-degree (resp. in-degree)

of v denoted d + (v) (resp. d -(v)
) is the size of its out-neighbourhood (resp. in-neighbourhood).

A tournament T of order 2k + 1 is regular if for any vertex v, we have

d + (v) = d -(v) = k.
Let X be a subset of V (T ). We denote by T -X the subtournament induced by the vertices V (T )\X. Furthermore, when X contains only one vertex {v} we simply write Tv instead of T -{v}. We also denote by T [X] the tournament induced by the vertices of X. Finally, we say that T [X] dominates T if, for every x ∈ X and every y ∈ V (T ) \ X, we have (x, y) ∈ A(T ). For more definitions on directed graphs, please refer to [START_REF] Bang-Jensen | Digraphs -Theory, Algorithms and Applications[END_REF].

Given a tournament T , we equip the vertices of T with is a strict total order ≺ σ . This operation also defines an ordering of the set of vertices denoted by σ := ⟨v 1 , . . . , v n ⟩ such that v i ≺ σ v j if and only if i < j. Given two distinct vertices u and v, if u ≺ σ v we say that u is before v in σ; otherwise, u is after v in σ. Additionally, an arc (u, v) is said to be forward (resp. backward ) if u ≺ σ v (resp. v ≺ σ u). A topological ordering is an ordering without any backward arcs. A tournament that admits a topological ordering does not contain a cycle. Hence, it is said to be acyclic.

A pattern p 1 := ⟨v 1 , . . . , v k ⟩ is a sequence of vertices that are consecutive in an ordering. Furthermore, considering a second pattern p 2 := ⟨u 1 , . . . , u k ′ ⟩ where {v 1 , . . . , v k } and {u 1 , . . . , u k ′ } are disjoint, the pattern ⟨p 1 , p 2 ⟩ is defined by ⟨v 1 , . . . , v k , u 1 , . . . , u k ′ ⟩. Degreewidth Given a tournament T , an ordering σ of its vertices V (T ) and a vertex v ∈ V (T ), we denote d σ (v) to be the number of backward arcs incident to v in σ, that is

d σ (v) := |{u | u ≺ σ v, u ∈ N + (v)} ∪ {u | v ≺ σ u, u ∈ N -(v)}|.
Then, we define the degreewidth of a tournament with respect to the ordering σ, denoted by ∆ σ (T ) := max{d σ (v) | v ∈ V (T )}. Note that ∆ σ (T ) is also the maximum degree of the underlying graph induced by the backward arcs of σ. Finally, we define the degreewidth ∆(T ) of the tournament T as follows.

Definition 1. The degreewidth of a tournament T , denoted ∆(T ), is defined as ∆(T ) := min σ∈Σ(T ) ∆ σ (T ), where Σ(T ) is the set of possible orderings for V (T ).

As mentioned before, this new parameter tries to measure how far a tournament is from being acyclic. Indeed, it is easy to see that a tournament T is acyclic if and only if ∆(T ) = 0. Additionally, when degreewidth of a tournament is one, it coincides with the notion of sparse tournaments, introduced in [8]. Remark. The definition of degreewidth naturally extends to directed graphs and we hope it will be an exciting parameter for problems on directed graphs. However, in this article we study this as a parameter for tournaments which is well-studied in various domains [START_REF] Allesina | A competitive network theory of species diversity[END_REF]9,[START_REF] Laslier | Tournament solutions and majority voting[END_REF]. Moreover, degreewidth also gives a succinct representation of a tournament. Informally, sparse graphs5 are graphs with a low density of edges. Hence, it may be surprising to talk about sparsity in tournaments. However, if a tournament on n vertices admits an ordering σ where the backward arcs form a matching, then it can be encoded by σ and the set of backward arcs (at most n/2). Thus, the size of the encoding for such tournament is O(n), instead of O(n 2 ). For a tournament with degreewidth k, the same reasoning implies that it can be encoded in O(kn) space.

Links to other parameters

Feedback arc/vertex set A feedback arc set (fas) is a collection of arcs that, when removed from the digraph (or, equivalently, reversed) makes it acyclic. The size of a minimum fas is considered for measuring how far the digraph is from being acyclic. In this context, degreewidth comes as a promising alternative. Finding a small subset of arcs hitting all substructures (in this case, directed cycles) of a digraph is one of the fundamental problems in graph theory. Note that we can easily bound the degreewidth of a tournament by its minimum fas f . Observation 1. For any tournament T , we have ∆(T ) ≤ |f |.

Proof. Consider a tournament T , and let σ f be an ordering of T for which the backward arcs are exactly the k arcs of a minimum feedback arc set of T . Then, for any vertex v ∈ V (T ), we have

d σ f (v) ≤ k. Therefore, ∆(T ) ≤ ∆ σ f (T ) ≤ k.
Note however that the opposite is not true; it is possible to construct tournaments with small degreewidth but large fas, see Figure 1(a). Similarly, a feedback vertex set (fvs) consists of a collection of vertices that, when removed from the digraph makes it acyclic. However, -unlike the feedback arc set -the link between feedback vertex set and degreewidth seems less clear; we can easily construct tournaments with low degreewidth and large fvs (see Figure 1(a)) as well as large degreewidth and small fvs (see Figure 1(b)).

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 (
Cutwidth Let us first recall the definition of the cutwidth of a digraph. Given an ordering σ := ⟨v 1 , . . . , v n ⟩ of the vertices of a digraph D, we say that a prefix of σ is a sequence of consecutive vertices ⟨v 1 , . . . , v k ⟩ for some k ∈ [n]. We associate for each prefix of σ a cut defined as the set of backward arcs with head in the prefix and tail outside of it. The width of the ordering σ is defined as the size of a maximum cut among all the possible prefixes of σ. The cutwidth of D, ctw(D), is the minimum width among all orderings of the vertex set of D.

Intuitively, the difference between the cutwidth and the degreewidth is that the former focuses on the backward arcs going "above" the intervals between the vertices while the latter focuses on the backward arcs coming from and to the vertices themselves. Observe that for any tournament T , the degreewidth is bounded by a function of the cutwidth. Formally, we have the following Observation 2. For any tournament T , we have ∆(T ) ≤ 2ctw(T ).

Proof. Consider a tournament T , and let σ c be an optimal ordering of T for the cutwidth. Then, let v be a vertex such that d σc (v) = ∆ σc (T ), the number of backward arcs with v as a tail (resp. with v as a head) cannot be larger than ctw(T ) without contradicting the optimality of σ c . Therefore, we have

∆ σ (T ) ≤ ∆ σc (T ) = d σc (v) ≤ 2ctw(T ).
Note however that the opposite is not true; it is possible to construct tournaments with small degreewidth but large cutwidth, see Figure 1(c). We remark that the graph problems that we study parameterized by degreewidth, namely, minimising fas, fvs, and dominating set are FPT w.r.t cutwidth [START_REF] Alber | Fixed parameter algorithms for dominating set and related problems on planar graphs[END_REF][START_REF] Chen | A fixed-parameter algorithm for the directed feedback vertex set problem[END_REF].

Degreewidth

In this section, we present some structural and algorithmical results for the computation of degreewidth. We first introduce the following lemma that provides a lower bound on the degreewith.

Lemma 1. Let T be a tournament. Then ∆(T ) ≥ min v∈V (T ) d -(v) and ∆(T ) ≥ min v∈V (T ) d + (v).
Proof. Consider an optimal ordering σ of T . Denote by u the first (resp. last) vertex according to this order. Clearly, u has d -(u) (resp. d + (u)) incident backwards arcs. Therefore, we have

∆(T ) ≥ d -(u) ≥ min v∈T (V ) d -(v) (resp. ∆(T ) ≥ d + (u) ≥ min v∈T (V ) d + (v)).

Degreewidth of regular tournaments

Theorem 1. Let T be a regular tournament of order 2k + 1. Then ∆(T ) = k. Furthermore, for any ordering σ, by denoting u and v respectively the first and last vertices in σ, we have

d σ (u) = d σ (v) = k.
Proof. Due to Lemma 1, ∆(T ) ≥ k. Suppose by contradiction that ∆(T ) > k. Let σ be an ordering of T such that ∆ σ (T ) = ∆(T ) which minimises the total number of backward arcs. Let the leftmost vertex of σ with d σ (v) > k be denoted by v. We construct an ordering σ ′ from σ by placing v at the first position (and not moving the other vertices). First we show that ∆ σ ′ (T ) ≤ ∆ σ (T ). Since v is first in σ ′ and T is regular, we have that d σ ′ (v) = k. Observe that since T is regular and d σ (v) > k, v is not the first vertex in σ. Suppose that the vertex w precedes v in σ. Then, since v is the leftmost vertex such that

d σ (v) > k, we have d σ (w) ≤ k. If (v, w) ∈ A(T ), then d σ ′ (w) = d σ (w) -1 < k. Otherwise, (w, v) ∈ A(T ), then d σ ′ (w) = d σ (w) + 1 ≤ k + 1 ≤ d σ (v).
Since the ordering between other vertices is the same in both σ and σ ′ , we have that ∆ σ ′ (T ) ≤ ∆ σ (T ). Now we show that the number of backward arcs in σ ′ is less than the number of backward arcs in σ which contradicts the minimality of σ.

Let L + = N + (v) ∩ {u | u ≺ σ v} be the set of out-neighbours of v on the left of v, L -= N -(v)∩{u | u ≺ σ v} the set of in-neighbours of v on the left of v, R + = N + (v) \ L + be the set of out-neighbours of v on the right of v and R -= N -(v) \ L -be the set of in-neighbours of v on the right of v in σ. Then d σ (v) = |L + | + |R -|.
The backward arcs from v to L + are forward arcs in σ ′ and the arcs from L -to v are now backward arcs incident to v in σ ′ . All the other arcs remain unchanged. As T is regular, we have

|L -| + |R -| = k and then d σ (v) = |L + | + (k -|L -|) > k. Thus, |L + | > |L -|.
Therefore, the total number of backward arcs of σ ′ is strictly smaller than σ.

This contradicts the minimality of σ. Hence, we conclude that ∆(T ) = k. The second part of the statement is immediate by regularity of the tournament.

Note that regular tournaments contain many cycles; therefore it is not surprising that their degreewidth is large. This corroborates the idea that this parameter measures how far a tournament is from being acyclic.

Computational complexity

We now show that computing the degreewidth of a tournament is NP-hard by defining a reduction from Balanced 3-SAT(4), proven NP-complete [START_REF] Berman | Approximation hardness of short symmetric instances of MAX-3SAT[END_REF] where each clause contains exactly three unique literals and each variable occurs two times positively and two times negatively.

Let φ be a Balanced 3-SAT(4) formula with m clauses c 1 , . . . , c m and n variables x 1 , . . . , x n . In the construction, we introduce several regular tournaments of size W or W +1 2 + n + m, where W is value greater than n 3 + m 3 . Note that n + m is necessarily odd since 4n = 3m. By taking a value W = 3 mod 4, we ensure that every regular tournament of size W or W +1 2 + n + m has an odd number of vertices. Construction 1. Let φ be a Balanced 3-SAT(4) formula with m clauses c 1 , . . . , c m clauses and n variables x 1 , . . . , x n such that n is odd and m is even. Let W = 3 mod 4 be an integer greater than n 3 + m 3 . We construct a tournament T as follows.

-Create two regular tournaments A and D of order

, q ′ 1 , . . . , q m , q ′ m ⟩ such that B ∪ D dominates Y and Y dominates A ∪ C. -For each clause c ℓ and each variable x i of φ, • if x i occurs positively in c ℓ , then {v i , v ′ i } dominates {q ℓ , q ′ ℓ }, • if x i occurs negatively in c ℓ , then {q ℓ , q ′ ℓ } dominates {v i , v ′ i }, A true zone B U Y C false zone D H
Fig. 2 Example of a nice ordering. A rectangle represents an acyclic tournament, while a rectangle with rounded corners represents a regular tournament.

A plain arc between two patterns P and P ′ represents the fact that there is a backward arc between every pair of vertices v ∈ P and v ′ ∈ P ′ . A dashed arc means some backward arcs may exist between the patterns.

• if x i does not occur in c ℓ , then introduce the paths

(v i , q ℓ , v ′ i ) and (v ′ i , q ′ ℓ , v i ). -Introduce an acyclic tournament U = {u p i , ūp i | i ≤ n, p ≤ 2} of order 4n such that U dominates A ∪ Y ∪ C and B ∪ D dominates U .
For each variable x i , add the following paths,

• for all variable x k ̸ = x i and all p ≤ 2, introduce the paths

(v k , u p i , v ′ k ) and (v ′ k , ūp i , v k ), • introduce the paths (v i , u 1 i , v ′ i ), (v ′ i , u 2 i , v i ), (v i , ū1 i , v ′ i ) and (v ′ i , ū2 i , v i ). -Finally, introduce an acyclic tournament H = {h 1 , h 2 } with topological or- dering ⟨h 1 , h 2 ⟩ and such that A ∪ B ∪ C ∪ X ∪ Y ∪ D dominates H and H dominates U .
We call a vertex of X a variable vertex and a vertex of Y a clause vertex. Furthermore, we say that the vertices (v i , v ′ i ) (resp. (q ℓ , q ′ ℓ )) is a pair of variable vertices (resp. pair of clause vertices). Definition 2. Let T be a tournament resulting from Construction 1. An ordering σ of T is nice if:

-∆ σ (A) = |A|-1 2 , ∆ σ (B) = |B|-1 2 , ∆ σ (C) = |C|-1 2 , and ∆ σ (D) = |D|-1 2 , -σ respects the topological ordering of U ∪ Y , -A ≺ σ B ≺ σ U ≺ σ Y ≺ σ C ≺ σ D ≺ σ H, and -for any variable x i , either A ≺ σ v i ≺ σ v ′ i ≺ σ B or C ≺ σ v i ≺ σ v ′ i ≺ σ D.
An example of a nice ordering is depicted in Figure 2. Let σ be a nice ordering, we call the pattern corresponding to the vertices between A and B, the true zone and the pattern after the vertices of C the false zone. Let (q ℓ , q ′ ℓ ) be a pair of clause vertices and let (v i , v ′ i ) be a pair of variable vertices such that x i occurs positively (resp. negatively) in c ℓ in φ. We say that the pair (v i , v ′ i ) satisfies (q ℓ , q ′ ℓ ) if v i and v ′ i both belong to the true zone (resp. false zone). Note that there is no backward arc between {q ℓ , q ′ ℓ } and {v i , v ′ i } if and only if (v i , v ′ i ) satisfies (q ℓ , q ′ ℓ ). Notice also that for any pair of variable vertices (v i , v ′ i ) such that x i does not appear in c ℓ and (v i , v ′ i ) is either in the true zone or in the false zone, then there is exactly two backward arcs between {q ℓ , q ′ ℓ } and {v j , v ′ j }.

Lemma 2. Let T be a tournament resulting from Construction 1 and let σ be a nice ordering of T . Then, we have ∆ σ (T ) ≤ W + 2m + 3n + 4. Moreover, for any vertex w ∈ V (T ) \ Y , we have d σ (w) < W + 2m + 3n + 4.

Proof. Let a be a vertex of A, there are at most |A|-1

2 = W +1 4 + m+n-1
+ 7m+11n 2 < W + 2m + 3n + 4. Let v be a vertex of X such that v ∈ {v i , v ′ i }
Y i = {q ℓ , q ′ ℓ | x i ∈ c ℓ }, if x i
occurs in the clause c ℓ , then there is 2 backward arcs between v and {q ℓ , q ′ ℓ } and none otherwise. Since x i occurs exactly two times positively and two times negatively, there are |Yi| 2 backward arcs between v and Y i . Moreover, by construction, there are exactly |Y \Yi|

2 between v and Y \ Y i . The number of backward arcs between v and Y is |Y | 2 + 2 = m. Thus, we have d σ (v) ≤ W + m + 4n. Since n < m, d σ (v) < W + 2m + 3n + 4.
Let u be a vertex of U . First, note that σ respects the topological ordering of U , we have d U (u) = 0. There are |H| = 2 backward arcs between u and H. There are |A| = W +1 2 +m+n backward arcs between u and |A| and |D| = W +1 2 +m+n backward arcs between u and D. Let (v i , v ′ i ) be a pair of variable vertices, since

v i ≺ σ v ′ i ≺ σ u or u ≺ σ v i ≺ σ v ′ i
, by construction there is exactly one backward arc between u and {v i , v ′ i }. Thus, there are |X| 2 = n backward arcs between u and |X|. Hence, d σ (u) = W + 2m + 3n + 3.

Let h be a vertex of H. There are |U | = 4n backward arcs between h and U and none between h and V (T )\U . Thus, we have d σ (h) = 4n < W +2m+3n+4.

Finally, let q ℓ be a vertex of Y . By construction, there are |A| = W +1 2 +m+n backward arcs between q ℓ and A and |D| = W +1 2 + m + n backward arcs between q ℓ . Let v i and v ′ i be a pair of variable vertices in X. If x i occurs in c ℓ , then there are at most two backward arcs between q ℓ and {v i , v ′ i }. If x i does not occur in c ℓ , then there is one backward arc between q ℓ and {v i , v ′ i }. Thus, there are at most n+3 backward arcs between q ℓ and X. Hence, we have d σ (q ℓ ) ≤ W +2m+3n+4.

To show the correctness of our reduction, we need to consider nice orderings. The following lemma transforms any ordering into a nice ordering. Lemma 3. Let T be a tournament resulting from Construction 1 and let σ be an ordering of T . There is a nice ordering

σ ′ of T such that ∆ σ ′ (T ) ≤ ∆ σ (T ).
Proof. Let σ be an ordering of T . First, if ∆ σ (T ) > W + 2m + 3n + 4, then by Lemma 2, for any nice ordering σ ′ of T we have ∆ σ ′ (T ) ≤ ∆ σ (T ). Thus, we can suppose that ∆ σ (T ) ≤ W +2m+3n+4. Second, if for any regular sub-tournament

T ′ among A, B, C or D, we have ∆ σ (T ′ ) > |T ′ |-1 2
, then by Theorem 1, we can rearrange the vertices of this tournament so that

∆ σ (T ′ ) ≤ |T ′ |-1 2
. Further, we show that it is possible to construct an ordering σ ′ with ∆ σ ′ (T ) ≤ ∆ σ (T ) and having the following properties:

Proof that A ≺ σ D: Let a ∈ A be the rightmost vertex of A and d ∈ D be the leftmost vertex of D. Toward a contradiction, suppose that d ≺ σ a. Let BC L = {t | t ∈ B ∪ C, t ≺ σ a} and BC R = {t | t ∈ B ∪ C, d ≺ σ t}. Note that BC L ∪ BC R = B ∪ C. If |BC L | > |BC R |, then |BC L | > |B∪C| 2 = W . Since A is a regular tournament, there are |A|-1 2
backward arcs between a and A \ {a}. Since BC L ≺ σ a, we have |BC L | backward arcs between BC L and a. Hence, we have

d σ (a) ≥ |A| -1 2 + |BC L | d σ (a) ≥ W -1 4 + m + n 2 + W d σ (a) ≥ 5W -1 4 + m + n 2 d σ (a) > W + 2m + 3n + 4.
We can prove similarly that if

|BC L | ≤ |BC R |,
+ |B L | + |D| which implies |A| -1 2 + |B L | + |D| < W + 2m + 3n + 4 W -1 4 + m + n 2 + W -|B R | + W + 1 2 + m + n < W + 2m + 3n + 4 |B R | > 3W 4 - m 2 - 3n 2 - 15 4 .
Now consider the vertex w. We have |B R | backward arcs between w and B R . Since w ≺ σ a, we have w ≺ σ D and thus, there are |D| backward arcs between w and D. We have

d σ (w) ≥ |B R | + |D| d σ (w) ≥ 3W 4 - m 2 - 3n 2 - 5 2 + W + 1 2 + m + n d σ (w) ≥ 5W 4 + m 2 - n 2 - 13 2 > W + 2m + 3n + 4.
variable vertex v ∈ X such that c ≺ σ v ≺ σ b. Let B L = {b ′ | b ′ ∈ B, b ′ ≺ σ v}, C L = {c ′ | c ′ ∈ C, c ′ ≺ σ v}, B R = B \ B L and C R = C \ C L . Suppose there is a vertex w ∈ U ∪ Y such that w ≺ σ v. Since A ≺ σ B, we have w ≺ σ B or A ≺ σ w. If w ≺ σ B, then by construction, we have d σ (w) ≥ |B| + |D| > W + 2m + 3n + 3 which is a contradiction. If A ≺ σ w, then d σ (w) ≥ |A| + |B R | + |D| which implies |A| + |B R | + |D| < W + 2m + 3n + 4 W + 2m + 2n + 1 + |B R | < W + 2m + 3n + 4 |B R | < n + 3. Moreover, by construction, d σ (v) ≥ |B L | + |C R |. Thus, |B L | + |C R | ≤ W + 2m + 3n + 4 2W -|B R | -|C L | ≤ W + 2m + 3n + 4 |B R | + |C L | ≥ W -2m -3n -4 |C L | ≥ W -2m -4n -7.
d σ (b) ≥ |B| -1 2 + |C L | d σ (b) ≥ W -1 2 + W -2m -4n -7 > W + 2m + 2n + 4.
By symmetry, we can use the argument to find a contradiction if there is a vertex

w ∈ U ∪ Y such that v ≺ σ w. Proof that B ≺ σ U ≺ σ Y ≺ σ C: Toward a contradiction, suppose that there are two vertices w ∈ U ∪ Y and c ∈ C such that c ≺ σ w. Suppose first that C ≺ σ w then we have d σ (w) ≥ |C| + |D| > W + 2m + 3n + 4 which is a contradiction. Then we can partition C into C L = {c | c ∈ C ∧ c ≺ σ w} and C R = C \ C L . We know that C R is not empty and since C ≺ σ D, we have w ≺ σ D. Then, we have d σ (w) ≥ |A| + |C L | + |D| which implies |A| + |C L | + |D| ≤ W + 2m + 3n + 4 2W + 2m + 2n + 1 -|C R | ≤ W + 2m + 3n + 4 |C R | ≥ W -n -3.
Now, as we did in the other cases, if there is no vertex v between c and w in σ such that (c, v) and (v, w) are forward arcs, we can exchange the positions of c and w in σ without increasing the degreewidth. Note that here we have several cases to consider: either v ∈ X or w ∈ U and v ∈ H. If v ∈ X, then using the previous inequality, we obtain

d σ (v) ≥ |B| + |C R | > W + 2m + 3n + 4 which is a contradiction. Now, if w ∈ U and v ∈ H then d σ (v) ≥ |C R | + |D| > W + 2m + 3n + 4, also a contradiction. Therefore, we have U ∪ Y ≺ σ C.
By symmetry, we can show that B ≺ σ U ∪Y , using the same arguments (note however that the case where w ∈ U and v ∈ H does not appear). Finally, since by construction U ∪ Y is an acyclic tournament, we can ordering the vertices of U ∪ Y so that U ≺ σ Y . Proof that A ≺ σ X ≺ σ D: If there are two vertices a ∈ A and v ∈ X such that v ≺ σ a, then by previous items, there is no clause vertex between v and a in σ. Thus, we can swap the positions of a and v in σ without increasing the degreewidth. That is, we can obtain an ordering σ ′ with A ≺ σ X. We prove similarly that X ≺ σ D.

Proof that D ≺ σ H: Let h be a vertex of H. If there is a vertex u ∈ U such that h ≺ σ u, then by the previous item h ≺ σ C ≺ σ D and thus, d σ (h) ≥ |C| + |D| > W + 2m + 3n + 4
which is a contradiction. Hence, we have U < h. By construction, we can put h after D in σ without increasing the degreewidth. That is, we can obtain an order σ ′ with D ≺ σ H. Proof that for any pair of variable vertices

(v i , v ′ i ), either v i ≺ σ v ′ i ≺ σ B or C ≺ σ v i ≺ σ v ′ i :
First, we show that for any vertex v ∈ X, we have either v ≺ σ B or C ≺ σ v (i.e. v is either in the true zone or the false zone). We can not have

B ≺ σ v ≺ σ C since otherwise we would have d σ (v) ≥ |B|+|C| ≥ 2W > W +2m+3n+4. If it exists a vertex b ∈ B such that b ≺ σ v ≺ σ C,
then any vertex between b and v in σ is a variable vertex or a vertex of B and, we can exchange the positions of c and v without increasing the degreewidth. If it exists a vertex c ∈ C such that B ≺ σ v ≺ σ c, then any vertex between c and v in σ is a variable vertex or a vertex of C and, we can exchange the positions of b and v without increasing the degreewidth. Now, let us show that for every pair v i and v ′ i of variable vertices, we have

v i ≺ σ v ′ i ≺ σ B or C ≺ σ v i ≺ σ v ′ i . Note that if v ′ i ≺ σ v i ≺ σ B or C ≺ σ v ′ i ≺ σ v i , then
we can exchange the positions of v i and v ′ i without increasing the degreewidth. Let v i and v ′ i be a pair of variable vertices, we say that

(v i , v ′ i ) is split if v i ≺ σ B and C ≺ σ v ′ i or if v ′ i ≺ σ B and C ≺ σ v i (i.e. if v i and v ′
i are not in the same zone). Recall that the number of backward arcs between any vertex u ∈ U and

V \ X is |A| + |D| + |H| = W + 2m + 2n + 3. Toward a contradiction let (v i , v ′ i ) be a split pair. Suppose that v i ≺ σ v ′ i .
Then, by construction, there are exactly two backward arcs between u p i and {v i , v ′ i } and two backward arcs between ūp i and {v i , v ′ i }. Always by construction, for each pair of variable vertices (v j , v ′ j ), there is exactly two backward arcs between {u 2 i , ū2 i } and {v j , v ′ j } (either both u 2 i and ū2 i are incident to a backward arc if (v j , v ′ j ) is not split or one of the two vertices is incident to two backward arcs). Suppose without loss of generality that the number of backward arcs between u 2 i and X \ {v i , v ′ i } is greater or equal to the number of backward arcs between ū2 i and X \ {v i , v ′ i }. That is, the number of backward arcs between u 2 i and X \ {v i , v ′ i } is at least n -1 and thus, the number of backward arcs between u 2 i and X is at least n+1. Hence,

d σ (u 2 i ) > W +2m+3n+4 which is a contradiction. By symmetry, if v ′ i ≺ σ v i , we can show that either d σ (u 1 i ) > W +2m+3n+4 or d σ (ū 1 i ) > W +2m+3n+4
which is a contradiction. Hence, no pair of variable vertices is split, that is, for each pair of variable vertices v i and v ′ i , we have

v i ≺ σ v ′ i ≺ σ B or C ≺ σ v i ≺ σ v ′ i .
Let φ be an instance of Balanced 3-SAT(4) and T its tournament resulting from Construction 1. We show that φ is satisfiable if and only if there exists an ordering σ of T such that ∆ σ (T ) < W + 2m + 3n + 4, which yields the following.

Theorem 2. Given a tournament T and an integer k, it is NP-complete to compute an ordering σ of T such that ∆ σ (T ) ≤ k.

Proof. Let φ be an instance of Balanced 3-SAT(4) and T its tournament resulting from Construction 1. We show that φ is satisfiable if and only if it exists an ordering σ of T such that ∆ σ (T ) < W + 2m + 3n + 4.

First, let β be a satisfying assignment for φ. We construct a nice ordering σ of T as follows. For each variable x i , if β(x i ) = true then put v i and v ′ i in the true zone. Otherwise, put v i and v ′ i in the false zone. By Lemma 2, for any vertex w ̸ ∈ Y , we have d σ (w) < W + 2m + 3n + 4. Further, let q ℓ be a clause vertex. The number of backward arcs between q ℓ and V (T ) \ X is equal to |A| + |D|. Moreover, for every variable x i that does not occur in c ℓ , there is exactly one backward arc between {v i , v ′ i } and q ℓ . For every variable x i ∈ c ℓ , if the value of x i in β satisfies c ℓ , then there is no backward arc between {v i , v ′ i } and q ℓ , otherwise there are two backward arcs between {v i , v ′ i } and q ℓ . Thus, since there is at least one variable in c ℓ that satisfies c ℓ , we have d σ (q ℓ ) ≤ W + 2m + 3n + 2. Hence, ∆ σ (T ) < W + 2m + 3n + 4. Now, let σ be an ordering of T such that ∆ σ (T ) < W + 2m + 3n + 4. By Lemma 3, we can suppose that σ is nice. We construct an assignment β for φ as follows. For each variable x i , if v i and v ′ i are in the true zone, then we set x i to true. Otherwise, if v i and v ′ i are in the false zone, then we set x i to false. Let c ℓ be a clause of φ. Since d σ (q ℓ ) < ∆ σ (T ) < W + 2m + 3n + 4, there is at least one pair of variable vertices v i and v ′ i such that there is no backward arcs between {v i , v ′ i } and q ℓ . Thus, by construction, x i satisfies c ℓ . Hence, β is a satisfying assignment for φ.

An approximation algorithm to compute degreewidth

In this subsection, we prove that sorting the vertices by increasing in-degree is a tight 3-approximation algorithm to compute the degreewidth of a tournament. Intuitively, the reasons why it returns a solution not too far from the optimal are twofold. Firstly, observe that the only optimal ordering for acyclic tournaments (i.e. with degreewidth 0) is an ordering with increasing in-degrees. Secondly, this strategy also gives an optimal solution for cutwidth in tournaments. Theorem 3. Ordering the vertices by increasing order of in-degree is a tight 3-approximation algorithm to compute the degreewidth of a tournament (see Figure 3).

Proof. Let T be a tournament, and consider σ app an ordering obtained by sorting the vertices of T in increasing order of in-degree. Let v be a vertex such that d σapp (v) = ∆ σapp (T ). Similarly, denote by σ opt an optimal ordering for T . First, notice that if there is a vertex u ∈ V (T ) such that 3d σopt (u) ≥ d σapp (v), then σ app is a 3-approximate solution. So we can assume that for each u ∈ V (T ), we

have d σopt (u) < dσ app (v) 3
. We consider three cases and show contradiction to this inequality in each of them.

Let us first define the following sets:

D + = {u ∈ V (T ) | (v, u) ∈ A(T ), u ≺ σapp v} and D -= {u ∈ V (T ) | (u, v) ∈ A(T ), v ≺ σapp u}. Note that d σapp (v) = |D + | + |D -|. Similarly, let R = {u ∈ V (T ) | v ≺ σapp u} and L = {u ∈ V (T ) | u ≺ σapp v}. We have d + (v) = |D + | + |R| -|D -| and d -(v) = |D -| + |L| -|D + |.
Now, suppose first that L ≺ σopt v (i.e. every vertex on the left of v in σ app remains on the left of v in σ opt ). We have

d σopt (v) ≥ |D + | which implies 2|D + | < |D -|. Let ℓ be the leftmost vertex of R in σ opt . Since d + (ℓ) ≤ d + (v), we have |N + (ℓ) ∩ R| ≤ |D + | + |R| -|D -|. Hence, d σopt (ℓ) ≥ |N -(ℓ) ∩ R| d σopt (ℓ) ≥ |R| -|N + (ℓ) ∩ R| d σopt (ℓ) ≥ |R| -|D + | -|R| + |D -| d σopt (ℓ) ≥ |D -| -|D + | d σopt (ℓ) ≥ d σapp (v) 3 , a contradiction.
Similarly, if v ≺ σopt R (i.e. every vertex on the right of v in σ app remains on the right of v in σ opt ), then we can show by symmetry that for the rightmost vertex

r of L in σ opt , we have d σopt (r) ≥ dσ app (v) 3
, a contradiction. Now suppose that there is at least one vertex of L on the right of v in σ opt and at least one vertex of R on the left of v in

σ opt . Let M R = {u | u ∈ D + , v ≺ σopt u} and M L = {u | u ∈ D -, u ≺ σopt v}. Since d σopt (v) < dσ app (v) 3 , we have |M L | + |M R | > 2dσ app (v) 3
. As we did before, let ℓ be the leftmost vertex of R in σ opt and r be the rightmost vertex of L in σ opt . Since

d + (ℓ) ≤ d + (v) (resp. d -(r) ≤ d -(v)), we have |N + (ℓ) ∩ (R ∪ M R )| ≤ |D + | + |R| -|D -| (resp. |N -(r) ∩ (L ∪ M L )| ≤ |D -| + |L| -|D + |). Further, since ℓ ≺ σopt v (resp. v ≺ σopt r), we have ℓ ≺ σopt M R ∪ R \ {ℓ} (resp. M L ∪ L \ {r} ≺ σopt r)
. Hence, we have

d σopt (ℓ) + d σopt (r) ≥ |N -(ℓ) ∩ (R ∪ M R )| + |N + (r) ∩ (L ∪ M L )| d σopt (ℓ) + d σopt (r) ≥ |R| + |M R | -|N + (ℓ) ∩ (R ∪ M R )| + |L| + |M L | -|N -(r) ∩ (L ∪ M L )| d σopt (ℓ) + d σopt (r) ≥ |R| + |M R | -|D + | -|R| + |D -| + |L| + |M L | -|D -| -|L| + |D + | d σopt (ℓ) + d σopt (r) ≥ |M R | + |M L | d σopt (ℓ) + d σopt (r) ≥ 2d σapp (v) 3 .
Therefore, we have either

d σopt (ℓ) ≥ dσ app (v) 3 or d σopt (r) ≥ dσ app (v) 3
, a contradiction. Finally, note that the approximation factor is tight as shown by Figure 3.

Results on sparse tournaments

In this section, we focus on tournaments with degreewidth one, called sparse tournaments. The main result of this section is that unlike in the general case, it is possible to compute in polynomial time a sparse ordering of a tournament (if it exists). We begin with an observation about sparse orderings (if it exists). Fig. 3 Example of a tournament where the approximate algorithm can return an ordering σ app (on the left) with degreewidth three while the optimal solution is one in σ opt (on the right). Coloured vertices are the ones incident to the maximum number of backward arcs. all non-depicted arcs are forward arcs.

Proof. Let σ be an ordering where there are at most i -2 vertices before v. Therefore, at least two vertices of N -(v) are after v in σ, proving it is not a sparse ordering.

Similarly, if we consider an ordering σ where there are at least i + 3 vertices before v. Therefore, at least two vertices of N + (v) are before v in σ, proving it is not a sparse ordering.

Note that Lemma 4 gives immediately an exponential running-time algorithm to decide if a tournament is sparse. However, we give in Subsection 4.2 a polynomial running-time algorithm for this problem. Before that we study a useful subclass of sparse tournaments, we call the U -tournaments.

U -tournaments

In this subsection, we study one specific type of tournaments called U -tournaments. Informally, they correspond to the acyclic tournaments where we reversed all the arcs of its Hamiltonian path. Definition 3. For any integer n ≥ 1, we define U n as the tournament on n vertices with

V (U n ) = {v 1 , v 2 , . . . , v n } and A(U n ) = {(v i+1 , v i ) | ∀i ∈ [n -1]} ∪ {(v i , v j ) | 1 ≤ i < n, i + 1 < j ≤ n}. We say that a tournament of order n is a U -tournament if it is isomorphic to U n .
Figures 4(a) and 4(d) depict respectively the tournaments U 7 and U 8 . This family of tournaments seems somehow strongly related to sparse tournaments and the following results will be useful later for both the polynomial algorithm to decide if a tournament is sparse and the polynomial algorithm for minimum feedback arc set in sparse tournaments. To do so, we prove that each U -tournament of order n > 4 has exactly two sparse orderings of its vertices that we formally define.

Definition 4. Let P (k) = ⟨v k+1 , v k ⟩ be a pattern of two vertices of U n for some integer k ∈ [n -1]. For any integer n ≥ 2, we define the following special orderings of U n :

if n is even:

• Π(U n ) is the ordering given by ⟨v 1 , P (2), P (4), . . . , P (n -2), v n ⟩.

• Π 1,n (U n ) is the ordering given by ⟨P (1), P (3), . . . , P (n -2), P (n)⟩.

U 7 : v 1 v 2 v 3 v 4 v 5 v 6 v 7
(a) The tournament U7.

Π 1 (U 7 ): v 2 v 1 v 4 v 3 v 6 v 5 v 7 (b)
The sparse ordering Π1(U7). Note that v1 is the only vertex not incident to any backward arc.

Π 7 (U 7 ): v 1 v 3 v 2 v 5 v 4 v 7 v 6
(c) The sparse ordering Π7(U7). Note that v7 is the only vertex not incident to any backward arc.

U 8 : v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 (d) The tournament U8. Π(U 8 ): v 1 v 3 v 2 v 5 v 4 v 7 v 6 v 8 (e)
The sparse ordering Π(U8). The dashed forward arcs is a minimum feedback arc set of the tournament. that all the vertices are incident to one backward arc.

Π 1,8 (U 8 ): v 2 v 1 v 4 v 3 v 6 v 5 v 8 v 7
(f) The sparse ordering Π1,8(U8). Note that v1 and v8 are the only vertices not incident to any backward arc.

Fig. 4 The tournaments U 7 and U 8 and their sparse orderings. The non-depicted arcs are forward arcs.

if n is odd:

• Π 1 (U n )
is the ordering given by ⟨P (1), P (3), . . . , P (n -2), v n ⟩.

• Π n (U n ) is the ordering given by ⟨v 1 , P (2), P (4), . . . , P (n -3), P (n -1)⟩. ) and Π 7 (U 7 ) (resp. Π(U 8 ) and Π 1,8 (U 8 )) of the tournament U 7 (resp. U 8 ). One can notice that these orderings are sparse and the subscript of Π indicates the vertex (or vertices) without a backward arc incident to it in this ordering. In the following, we prove that when n > 4 there are no other sparse orderings of U n . However, note that there are three possible sparse orderings of U 3 (namely, Π 1 (U 3 ) and Π 3 (U 3 ) defined previously, as well as Π 2 (U 3 ) := ⟨v 3 , v 2 , v 1 ⟩) and three sparse orderings of U 4 (namely, Π(U 4 ), Π 1,4 (U 4 ) as defined before, and

Π ′ (U 4 ) := ⟨v 2 , v 4 , v 1 , v 3 ⟩).
In order to prove that there are no other sparse orderings of U n , we start by giving some properties on the position of the vertices; specifically, we refine the statement of Lemma 4 in the case where the tournament is U n . Lemma 5. In any sparse ordering σ of U n , the position of v 1 (and v n ) is either 1 or 2 (resp. n or n -1). Furthermore, there are no pattern

⟨v i , v i+1 ⟩ in σ for each i ∈ [n -1].
Proof. We prove the first statement for the vertex v 1 . Using Lemma 4, we already know that v 1 is either at position 1, 2 or 3. Suppose the latter, so there are exactly two vertices before v 1 . By construction, one of these two vertices has to be v 2 and let v k be the other vertex before v 1 , where k ≥ 3. If in addition we have k < n, then let us consider the vertex v k+1 which is after v k in σ. Therefore, we have d σ (v k ) ≥ 2, proving σ is not a sparse ordering. If k = n > 4, then v 3 is after v n , so we also have d σ (v n ) ≥ 2. The proof for the vertex v n is similar. on which we will also insert v n+1 , then by Lemma 5 we can only insert v n+1 at position n, and we obtain exactly Π 1,n+1 (U n+1 ).

Since in every case, the vertex v n+1 has no other possible position, it proves that there are no other sparse orderings of U n+1 , concluding the proof.

A polynomial time algorithm for sparse tournaments

We give here a polynomial algorithm to compute a sparse ordering of a tournament (if any). First of all, let us recall a classical algorithm to compute a topological ordering of a tournament (if any): we look for the vertex v with the smallest in-degree; if v has in-degree one or more, we have a certificate that the tournament is not acyclic. Otherwise, we add v at the beginning of the ordering, and we repeat the reasoning on Tv, until V (T ) is empty.

The idea of the original "proof" in [25, Lemma 35.1, p.97] was similar: considering the set of vertices X of smallest in-degrees, put X at the beginning of the ordering, and remove X from the tournament. However, potential backward arcs from the remaining vertices of V \ X to X may have been forgotten. For example, consider a tournament over 9 vertices consisting of a U 5 (with vertex set {v 1 , . . . , v 5 }) that dominates a U 4 (with vertex set {u 1 , ..., u 4 }) except for the backward arc (u 4 , v 5 ). It is sparse (⟨Π 5 (U 5 ), Π 1,4 (U 4 )⟩) but the algorithm returns the (non-sparse) ordering ⟨Π 1 (U 5 ), Π 1,4 (U 4 )⟩ (v 5 is incident to two backward arcs). The problem is that this algorithm is too "local"; it will always prefer the sparse ordering Π 1 (U 2k+1 ) over Π 2k+1 (U 2k+1 ), but it may be necessary to take the latter. Therefore, to correct this, we needed a much more involved algorithm, requiring the study of the U-tournaments and the notion of quasi-domination (see Definition 6). Indeed, unlike the algorithm for the topological ordering, we may have to look more carefully how the vertices with low in-degrees are connected to the rest of the digraph. These correspond to the case where there exists a U -sub-tournament of T which either dominates or "quasidominates" (see Definition 6) the tournament T . Because of the latter possibility (where a backward arc (a, b) is forced to appear), we need to look for specific sparse orderings, called M -sparse orderings (where a or b should not be endvertices of other backward arcs). As all the sparse orderings for U -tournaments have been described, we can derive a recursive algorithm. Definition 5. Let T be a tournament, X be a subset of vertices of T , and M be a subset of X. We say

T [X] is M -sparse if there exists an ordering σ of X such that ∆ σ(T [X]) (X) ≤ 1 and d σ (v) = 0 for all v ∈ M . In that case, σ is said to be an M -sparse ordering of T [X]. For example, U 4 [{v 1 , v 2 , v 3 }] is {v 2 }-sparse, because there exists a sparse ordering σ := ⟨v 3 , v 2 , v 1 ⟩ of U 4 [{v 1 , v 2 , v 3 }] such that d σ (v 2 ) = 0.
We remark that T is sparse if and only if T is ∅-sparse. In fact, the algorithm described in this section computes a ∅-sparse ordering of the given tournament (if any). Observation 3. Let T be a tournament and X and M be subsets of vertices of

T . If T is M -sparse, then T [X] is M ∩ X-sparse.
Proof. Consider σ an ordering of the vertices of T such that it is M -sparse. The restriction of σ to the vertices of X is also a sparse ordering, and d σ (v) = 0 for all v ∈ M ∩ X. Thus T [X] is also M ∩ X-sparse. Lemma 6. Let T be a tournament, let X and M be two subsets of

V (T ) such that T [X] dominates T . Then, T is M -sparse if and only if T [X] is M ∩X-sparse and T -X is M \ X-sparse. Proof. Suppose that T [X] is M ∩ X-sparse and that T -X is M \ X-sparse.
Then by concatenating the orderings, we obtain a M -sparse ordering for T . This follows from the fact that we do not create any additional backward arcs by concatenating since X dominates T -X.

Suppose that T is M -sparse. Then by Observation 3,

T [X] is M ∩ X-sparse and T -X is M \ X-sparse.
Corollary 1. Let T be a tournament and v be a vertex such that d

-(v) = 0. Let M be a subset of V (T ). Then T is M -sparse if and only if T -v is M \{v}-sparse.
Lemma 7. Let T be a tournament such that there exists a unique vertex v with d -(v) = 1 and all the other vertices have in-degree at least two. Let w be the unique in-neighbour of v and M be a subset of vertices of V (T ).

Then T is M -sparse if and only if v ̸ ∈ M and T -v is M ∪ {w} \ {v}-sparse.
Proof. Suppose first that T is M -sparse. Note that in any sparse ordering, the first vertex is necessarily v otherwise any vertex placed at the first would have two backward arcs incident to it, that is, the ordering would not be sparse. Therefore, in any sparse ordering, there is a backward arc from w to v. Thus, we have v ̸ ∈ M . Consider now a M -sparse ordering σ := ⟨v, σ ′ ⟩ of T . Then, σ ′ is also a sparse ordering of T -v. Furthermore, notice that we have ∆ σ ′ (w) = 0, as there is already a backward arc from w to v in σ. Thus σ ′ is a M ∪ {w} \ {v}-sparse ordering of Tv.

For the other direction, suppose that v ̸ ∈ M and Tv is M ∪ {w} \ {v}sparse and let σ ′ be a M ∪ {w} \ {v}-sparse ordering of Tv. Consider now the following ordering σ := ⟨v, σ ′ ⟩ of T . Note that σ is sparse since there is only one backward arc incident to v, namely (w, v). Therefore, σ is a M -sparse ordering since σ ′ is a M ∪ {w} \ {v}-sparse ordering.

Definition 6 (see Figure 5). Given a tournament T and two of its vertices a and b, we say that a subset of vertices X quasi-dominates T if:

there exists an arc (b, a)

∈ A(T ) such that a ∈ X and b ̸ ∈ X, -(u, v) ∈ A(T ) for every (u, v) ∈ (X × (V (T ) \ X)) \ {(a, b)}, -d -(b) ≥ |X| + 1,
and the vertex a has an out-neighbour in X. In this case, we also say X (b, a)-quasi-dominates T .

Lemma 8. Let T be a tournament, X be a subset of vertices of T , and a and b be two vertices such that X (b, a)-quasi-dominates T . Furthermore, let M be a subset of V (T ). Proof. Suppose first that X is (M ∪ {a}) ∩ X-sparse and that T -X is (M ∪ {b}) \ X-sparse (see Figure 6 for an example). We want to define a M -sparse ordering of T . To do so, let σ ′ be a (M ∪ {a}) ∩ X-sparse ordering of X and σ ′′ be a (M ∪ {b}) \ X-sparse ordering of T -X. We define the ordering of T , let σ := ⟨σ ′ , σ ′′ ⟩. Note that σ is a sparse ordering. Indeed, for every vertex v different from a and b, we have d σ (v) ≤ 1. Furthermore, we also have Suppose now that T is M -sparse, and consider σ a M -sparse ordering of T . If a ≺ σ b, then (b, a) is a backward arc and d σ (a) = d σ (b) = 1. Therefore, the restriction of σ to X is (M ∪ {a}) ∩ X-sparse (as b ̸ ∈ X). Furthermore, the restriction of σ to T -X is (M ∪ {b}) \ X-sparse (as a ̸ ∈ V \ X). So we proved the statement in this case.

Then T is M -sparse if and only if T [X] is (M ∪ {a}) ∩ X-sparse and T -X is (M ∪ {b}) \ X-sparse
d σ (a) = d σ (b) = 1 since (b, a) ∈ A(T )
Let us now consider the case b ≺ σ a. As d -(b) ≥ |X| + 1 and as every vertex of X except a is an in-neighbour of b, then there exist two vertices b ′ and b

′′ in V \ X such that (b ′ , b) ∈ A(T ) and (b ′′ , b) ∈ A(T ). Note that since d σ (b) ≤ 1, either b ′ or b ′′ must be before b in the ordering. Without loss of generality, suppose that b ′ ≺ σ b. By definition, a has an out-neighbour in X, call it a ′ . Then (a ′ , b ′ ) ∈ A(T ).
If a ≺ σ a ′ , then b ′ has at least two backward arcs: (a ′ , b ′ ) and (a, b ′ ), which contradicts the ordering σ being sparse. Thus a ′ ≺ σ a and so a has at least two backward arcs: (a, a ′ ) and (a, b ′ ). We also reach a contradiction, proving the case b ≺ σ a is impossible, and concluding the proof. Definition 7. Let T be a tournament and X = (v 1 , . . . , v k ) be a list of vertices with k ≥ 2. We say that X satisfies the U -property if d -(v 1 ) = 1 and for each i ∈ {2, . . . , k}, we have We can create the algorithm isUkMsparse which given (v 1 , . . . , v k ) a Utournament and M a subset of these vertices, returns a boolean which is True if and only if this tournament is M -sparse. We can also create the algorithm getUsubtournament which given T a tournament, and X = (u 1 , . . . , u k ) a list of vertices such that d -(u 1 ) = 1 and d -(u i ) = i -1 and (u i , u i-1 ) ∈ A(T ) for all i ∈ {2, . . . , k}, returns a U -subtournament dominating or quasi-dominating T . With these two previous algorithms, we can derive Algorithm 3 isMsparse.

(v i , v i-1 ) ∈ A(T ) and d -(v i ) = i -1. Algorithm 3: isMsparse Data: T a tournament, M a subset of the vertices of T Result: True if T is M -sparse and False otherwise 1 if |V (T )| ≤ 1 then return True ; 2 else if min v∈V (T ) d -(v) ≥ 2 then return False ; 3 else if min v∈V (T ) d -(v) = 0 then 4 v ←-the vertex of in-degree 0; 5 return isMsparse(T -v, M \ {v}); 6 else if |{v ∈ V (T ) : d -(v) = 1}| = 1 then 7 v, w ←-two vertices such that d -(v) = 1 and (w, v) ∈ A(T ); 8 return v ̸ ∈ M and isMsparse(T -v, (M ∪ {w}) \ {v}); 9 else 10 v, w ←-two vertices of in-degree 1 such that (w, v) ∈ A(T ); 11 X ←-getUsubtournament(T ,(v, w)); 12 if X dominates T then 13 return ( isUkMsparse(X,M ∩ X) and isMsparse(T -X, M \ X));

Algorithm 1: getUsubtournament

Data: T a tournament, and X = (u1, . . . , u k ) a list of vertices such that d -(u1) = 1 and d -(ui) = i -1 and (ui, ui-1) ∈ A(T ) for all i ∈ {2, . . . , k}. Result: A U -subtournament dominating or quasi-dominating T .

1 w ←-a vertex of N -(u k ) \ X; 2 if d -(w) = d -(u k ) then return X ∪ {w}
/* this set dominates T */ ;

3 else if d -(w) = d -(u k ) + 1 then return getUsubtournament(T, X ∪ {w}) ; 4 else return X /* this set (w, u k )-quasi-dominates T */ ; Algorithm 2: isUkMsparse Data: (v1, . . . , v k ) a U k tournament, M a subset of the vertices of U k Result: True if U k is M -sparse and False otherwise 1 if k ≤ 2 then return True ; 2 else if k = 3 then return |M | ≤ 1 ; 3 else if k is even then return |M \ {v1, v k }| = 0 ; 4 else if k is odd then return (v1 ̸ ∈ M or v k ̸ ∈ M ) and |M \ {v1, v k }| = 0 ;
Theorem 5. Algorithm 3 is correct. Hence, it is possible to decide if a tournament T with n vertices is sparse in O(n 3 ) by calling isMsparse(T ,∅).

Proof. Let us show that Algorithm 2 is correct. If k ≤ 2, then U 2 is M -sparse for any subset M of vertices of U 2 as there is an ordering of U 2 without backward arcs (line 1). If k = 3, there are only 3 sparse orderings of U 3 . As the description of these sparse orderings has been seen, we can see that U 3 is M -sparse if and only if M contains at most 1 vertex (line 2). If k ≥ 4 and k is even, we have showed that there is a sparse ordering where every vertex is adjacent to a backward arc and exactly one other sparse ordering where only v 1 and v k are not adjacent to a backward arc. Thus U k is sparse if and only if there does not exist i ∈ {2, . . . , k -1} such that v i ∈ M . In other words U k is M -sparse if and only if M \ {v 1 , v k } = ∅ (line 3). If k ≥ 4 and k is odd, we have showed that there exists exactly two sparse orderings of U k : one where v 1 is the only vertex not adjacent to a backward arc and one another where v k is the only vertex not adjacent to a backward arc. Thus U k is M -sparse if and only if M does not contain both v 1 and v k (otherwise none of the two previous sparse orderings fit the condition) and M does not contain a vertex v i such that i ∈ {2, . . . , k -1}. In other words

U k is M -sparse if and only if {v 1 , v k } ̸ ⊂ M and M \ {v 1 , v k } = ∅ (line 4). Thus, we show that for each value of k ∈ [n], Algorithm 2 correctly decides if U k is M -sparse.
Algorithm 1 is correct by Lemma 10.

Let us show that Algorithm 3 is correct. If T is constituted by a single vertex then T is trivially sparse (line 1). If min v∈V (T ) d -(v) ≥ 2, then by Lemma 1, T is not sparse (line 2). If T has a vertex v of in-degree zero, then by Corollary 1, T is M -sparse if and only if T -v is M \{v}-sparse (lines 5). Otherwise, there exists a vertex v such that d -(v) = 1. If v is the unique vertex of in-degree one, then by Lemma 7, T is M -sparse if and only if v ̸ ∈ M and Tv is (M ∪ {b}) \ {v}-sparse (where b is the unique in-neighbour of v) (line 9). Otherwise, there exist at least two vertices v and w of in-degree one. By Lemma 10, there exists X such that either X dominates T , or X quasi-dominates T . If X dominates T , then T is M -sparse if and only if X is M ∩ X-sparse and T -X is M \ X-sparse due to Lemma 6 (line 14). Otherwise, there exists two vertices a and b such that X (b, a)-quasi-dominates T , then by Lemma 8, T is M -sparse if and only if X is (M ∪ {a}) ∩ X-sparse and T -X is (M ∪ {b}) \ X-sparse (line 17).

Let us now investigate the time complexity of the algorithms. Observe that we can easily modify Algorithm 3 to obtain a sparse ordering (if exists). Next corollary follows from the above algorithm.

v ∈ V (G) \ X, we have N + (v) ∩ X ̸ = ∅.
Observe that in graphs where degreewidth is zero, DS is of size one. Similarly, for tournaments with degreewidth equals to one, the DS is of size at most two. That is, we have trivial solutions for DS for acyclic and sparse tournaments. This motivates us to look for FPT algorithm parameterized by degreewidth. In the following, we develop an FPT algorithm for Dominating Set using universal families. Before that we observe that size of a dominating is always bounded by the size of degreewidth.

Observation 5. The size of a minimum dominating set of a tournament T is at most ∆(T ) + 1.

Proof. Consider an ordering σ of T such that ∆ σ (T ) is the degreewidth of T . Then, the first vertex v in σ dominates every vertex except the ones from which there is a backward arc incident to it. Therefore, {v}∪N -(v) is a dominating set of T . Since v is the first vertex in σ, the size of N -(v) is bounded by degreewidth. Hence, the statement follows. Theorem 6. Dominating Set is FPT in tournaments with respect to degreewidth.

Proof. Let T be a tournament with degreewidth bounded by some integer k. We want to compute a dominating set of T of size at most s. Using Theorem 3, we can find a 3-approximation for degreewidth. Let σ be the ordering given by Theorem 3. Therefore, we have ∆ σ (T ) ≤ 3k.

Our algorithm proceeds in two steps as described below. First is the separation phase where we define a subgraph of T and use n-p-q-lopsided universal family to identify a solution. Next, we verify it. To state the algorithm formally, we first define n-p-q-lopsided universal families.

Given a universe U and an integer i, we denote all the i-sized subsets of U by U i . We say that a family F of sets over a universe U with |U | = n, is an n-p-q-lopsided universal family if for every A ∈ U p and B ∈ U \A q , there is an F ∈ F such that A ⊆ F and B ∩ F = ∅.

Lemma 11 ( [16]

). There is an algorithm that given n, p, q ∈ N constructs an n-p-q-lopsided universal family F of cardinality p+q p • 2 o(p+q) log n in time |F|n.

Let |V (T )| = n. We fix an arbitrary ordering of the vertices V (T ) and write V (T ) as [n] and for X ⊆ [n], we write T [X] to denote the tournament induced on X. The algorithm is described as follows.

1. For each integer 1 ≤ p ≤ s, we construct an n-p-3kp-lopsided universal family F using the algorithm in Lemma 11.

2. Then, for each F ∈ F, let C 1 , . . . , C ℓ be the strongly connected components of T [F ], ordered according to their first vertex in σ (i.e. the first vertex of C i is before all the vertices of C j in σ for each j > i). Check if C 1 is a dominating set for T . If so, we return C 1 , otherwise it is a no-instance.

We now show the correctness of our algorithm. Suppose (T, s) is a yesinstance. Let S denote a dominating set of size s of T . Let N = {v ∈ N + (S) \ S | v ≺ σ u, for some u ∈ S}. Observe that |N | ≤ 3ks. From the definition of ns-3ks-lopsided universal family, we have that there exists a set F ∈ F such that S ⊆ F, and

N ∩ F = ∅. (1)
Now we show that if C i ∩ S ̸ = ∅ for some i ∈ [ℓ], then C i ⊆ S. Suppose not. Let v ∈ C i ∩ S, and let u be a vertex of C i \ S. Since C i is strongly connected, let (u := v 1 , v 2 , . . . , v p := v) be a path from u to v in C i . The vertex u ∈ F , so it is not in N by [START_REF] Allesina | A competitive network theory of species diversity[END_REF]. Furthermore, it is not in S by definition. So by definition of N , u is not incident to any vertex of S. So v 2 ∈ C i \ S. By repeating this reasoning, we obtain v / ∈ S, a contradiction. Finally, we show that C 1 is a dominating set of T of size at most s. Suppose not. Let C i be the first strongly connected component in S for some i > 1. Note that given two distinct strongly connected components C j and C j ′ with j < j ′ , there is, by definition, no arc between them in T [F ], and therefore in T . So there is no backward arcs from C j ′ to C j in T . This observation shows that C i does not dominate the vertices of C 1 , . . . , C i-1 in T . Similarly, the vertices of C 1 , . . . , C i-1 cannot be dominated by any vertices of C j for any j > i. So S is not a dominating set of T , a contradiction. Therefore, we can return the vertices of C 1 as a solution of Dominating Set in T . The algorithm invokes Lemma 11 s times. Hence, it runs in time 2 O(s log(s(3k+1)) n O (1) . Finally, Observation 5 gives the theorem.

FAST and FVST in sparse tournaments

A forbidden pattern corresponds to the patterns Π(U 2k ) for any k ≥ 1 as well as Π ′ (U 4 ) := ⟨v 2 , v 4 , v 1 , v 3 ⟩. An example of the forbidden pattern Π(U 8 ) is depicted in Figure 4(e). We say a sparse ordering has forbidden pattern if a contiguous subsequence of the ordering is a forbidden pattern. Intuitively, the problem of such patterns is that the set of their backward arcs is not a minimum fas. Hopefully, we can use Theorem 4 in such a way that if the pattern Π(U 2k ) appears, we can restructure it into Π 1,2k (U 2k ). Lemma 12. Let T be a sparse tournament on n vertices. Then, it is possible to construct in time O(n 3 ) a sparse ordering for T without forbidden patterns.

Proof. Let σ be a sparse ordering of T where for some 2 ≤ 2k ≤ n, the vertices {v 1 , . . . , v 2k } form the forbidden pattern Π(U 2k ) (or Π ′ (U 4 )). That is, σ := ⟨σ 1 , Π(U 2k ), σ 2 ⟩ (resp. ⟨σ 1 , Π ′ (U 4 ), σ 2 ⟩). Let σ ′ be the ordering we get by replacing Π(U 2k ) by Π 1,2k (U 2k ). That is, σ ′ := ⟨σ 1 , Π 1,2k (U 2k ), σ 2 ⟩. Observe that σ ′ is a sparse ordering. Let us now show that there is no vertex of v 1 , . . . , v 2k lying in a forbidden pattern in σ ′ . By contradiction, suppose that σ ′ has a forbidden pattern Π(U 2k ′ ) (or Π ′ (U 4 )) for some 2 ≤ 2k ′ ≤ n on the subset of vertices V ′ .

Case 1: {v 1 , . . . , v 2k } ⊆ V ′ . This is not possible since it is easy to see that the pattern Π 1,2k (U 2k ) cannot be contained in the pattern Π(U 2k ′ ) (resp. Π ′ (U 4 )).

Case 2: |{v 1 , . . . , v 2k } ∩ V ′ | ≥ 1. Then, since the patterns are consecutive sequence of vertices, either the first or the last vertex of Π

1,2k (U 2k ) is in V ′ . Without loss of generality, suppose that the first vertex of Π 1,2k (U 2k ) is in V ′ , that is, v 2 ∈ V ′ . Note that v 2 has a backward arc incident to it in Π 1,2k (U 2k ). Since σ ′ is a sparse ordering, v 2 cannot have another backward arc to/from a vertex in V ′ . Hence, v 2 can not form the forbidden pattern Π(U 2k ′ ) (resp. Π ′ (U 4 )) in V ′ .
Hence, in both cases, we have a contradiction. Thus, no forbidden pattern containing a vertex from v 1 , . . . , v 2k is in σ ′ . Therefore, given a sparse ordering σ of T , we can replace the forbidden patterns and obtain a sparse ordering of T containing no forbidden patterns. Next we show that we can do it in time O(n). The correctness of the following process follows from the above argument.

Given a sparse ordering σ := ⟨v 1 , v 2 , . . . , v n ⟩, we first check there is no arc (v i+1 , v i ). If so, we swap these vertices in the ordering. Then, we check similarly for the pattern Π ′ (U 4 ) for every four consecutive vertices and replace them with Π 1,4 (U 4 ). We can now assume σ is a sparse ordering without these patterns. Now, we define the span of an arc in an ordering σ to be the number of vertices between its end-vertices in σ, including the end-vertices. For example, let σ := ⟨v 1 , v 2 , . . . , v n ⟩, then in Π(U 2k ) for some k ≥ 2, the span of the arc (v 3 , v 1 ) is three. Note that the sequence of backward arcs in Π(U 2k ) (taken from left to right) starts and ends with backward arcs of span of three, with (eventually) backward arcs of span four in between. The idea of the following algorithm is to look for such sequences.

We try to look for the sequence Π(U 2k ) from left, for some k ≥ 2. We check for the backward arc (v s+2 , v s ) of span three with minimum position s. Then, we continue to look for backward arcs of span four and stop at a backward arc of span three as described next. We continue as long as there is an arc (v s+2i+4 , v s+2i+1 ) ∈ A(T ) for i ≥ 0. Suppose that we end at i = t such that s + 2t + 4 < n, then we check if (v s+2t+5 , v s+2t+3 ) ∈ A(T ).

If so, we have found the forbidden pattern Π(U 2t+6 ) on the vertices {v s , . . . , v s+2t+5 }. We reorder this pattern according to the order Π 1,2t+6 (U 2t+6 ) in σ. We repeat the process from the vertex v s+2t+7 by checking for a backward arc of span three.

If not, we repeat the process starting from the vertex v s+2t+5 . Hence, we replace all the forbidden patterns in time O(n) by the above left to right scan. Since by Theorem 5, a sparse ordering σ of T can be constructed in O(n 3 ) time, we have proved the lemma.

If a sparse ordering does not contain a forbidden pattern then its set of backward arcs is a fas. Hence, we obtain the following result.

Theorem 7. FAST is solvable in time O(n 3 ) in sparse tournaments on n vertices.

Proof. Let T be a sparse tournament and let σ be a sparse ordering without forbidden patterns of V (T ) computed using lemma 12. We prove that the set of backward arcs of T in the ordering σ is a minimum feedback arc set of T . In the following, let B = ((u 1 , v 1 ), . . . , (u k , v k )) be the set of backward arcs defined by the ordering σ. The set B is ordered from the left to right according to the head of the arcs, that is, the arc (u i , v i ) appears before the arc (u j , v j ) if v i ≺ σ v j . Let S be any feedback arc set. To show that B is a minimum feedback arc set, we construct an injective function f : B → S in the following way. We start with the function f : B → {∅} and then we assign iteratively a backward arc of B to an arc of S according to the order of B from (u 1 , v 1 ).

Let (u i , v i ) be a backward arc of B to assign (all the backward arcs (u j , v j ) with j < i have already been assigned). Let x i be the vertex right after v i in σ. We have x i ̸ = u i since otherwise ⟨u i , v i ⟩ would be isomorphic to the forbidden pattern Π(U 2 ). Thus, (v i , x i , u i ) is a cycle (as σ is a sparse ordering) and there is at least one arc in S among (v i , x i ), (x i , u i ), and (u i , v i ) (as S is a feedback arc set). We consider the following four cases.

(a) If (u i , v i ) ∈ S, then we set f ((u i , v i )) := (u i , v i ). (b) If (u i , v i ) ̸ ∈ S and (x i , u i ) ∈ S, then we set f ((u i , v i )) := (x i , u i ). (c) If (u i , v i ) ̸ ∈ S, (x i , u i ) ̸ ∈ S and f -1 ((v i , x i )) = ∅, then we set f ((u i , v i )) := (v i , x i ). (d)
Otherwise, let y i be the vertex right after the vertex x i in σ. We will show later that y i ̸ = u i . Since (v i , y i , u i ) is a cycle, there is an arc a in S ∩ {(v i , y i ), (y i , u i )}. We set f ((u i , v i )) := a.

We now show the correctness of case (d). We have to show that y i ̸ = u i . Toward a contradiction, suppose that y i = u i . As we are not in cases (a), (b) or (c), (v i , x i ) ∈ S and there exists (u j , v j ) ∈ B such that f (u j , v j ) = (v i , x i ) and j < i.

The arc (u j , v j ) has been assigned to (v i , x i ) as a case (b) or (d), thus u j = x i .

There is at most one vertex between v j and v i since otherwise, v i ̸ ∈ {x j , y j } and thus we would not have f ((u j , v j )) = (v i , x i ). There is at least one vertex between v j and v i , since otherwise ⟨v j , v i , x i , u i ⟩ would be forbidden pattern Π(U 4 ). Therefore, there is exactly one vertex x j between v j and v i then, there is a backward arc adjacent to x j since otherwise we would have f ((u j , v j )) = (v j , x j ) or f ((u j , v j )) = (x j , v i ) from cases (b) or (c). This backward arc is leaving x j , since otherwise this backward arc would be assigned after (u j , v j ) and therefore (u j , v j ) would be assigned in same way as before. Thus, we have j = i -1 and (x i , v i-1 ) has been assigned to (v i , x i ) as a case (d). By induction, it exists a pattern ⟨v ℓ , x ℓ = v ℓ+1 , u ℓ = x ℓ+1 , y ℓ+1 = v ℓ+2 , . . . , y i-2 = v i-1 , x i-1 = u i-2 , y i-1 = v i , u i-1 = x i , u i ⟩ in σ which is a forbidden pattern. Hence, y i ̸ = u i .

h ≺ σ x ≺ σ t, we have x ∈ X. Note that if a backward arc (t, h) is saturated then every cycle C that contains only (t, h) as a backward arc is eliminated when X is deleted. Moreover, since X is a feedback vertex set, if (t, h) is not saturated, then {t, h} ∩ X ̸ = ∅.

Lemma 13. Let T be a tournament resulting from Construction 2 along with the sparse ordering σ. Let X be a solution for FVST in T . There is a solution X ′ such that |X ′ | ≤ |X|:

for every edge backward arc (u i j , u j i ), we have |{u i j , u j i } ∩ X ′ | = 1, and for every v ∈ X ′ , v is adjacent to a backward arc.

Proof. First, we show that we can construct a solution X ′ such that for every edge backward arc (u i j , u j i ) we have {u i j , u j i }∩X ′ ̸ = ∅. Let (u i j , u j i ) be the leftmost edge backward arc such that {u i j , u j i }∩X = ∅. It means that (u i j , u j i ) is saturated and so {x 1 i , x 2 i , x 3 i } ⊂ X. Let v k and v ℓ be the two neighbours of v i different from v j in G. We set X ′ = X ∪ {u j i , u k i , u ℓ i } \ {x 1 i , x 2 i , x 3 i }. We now show that X ′ is a solution to FVST. Let C be a cycle containing x ∈ {x 1 i , x 2 i , x 3 i }. C necessarily contains a backward arc (u, v) such that v ≺ σ x ≺ σ u and by construction (u, v) is an edge backward arc. If v ≺ σ u i j then by hypothesis {u, v} ∩ X ̸ = ∅ and thus, {u, v} ∩ X ′ ̸ = ∅ which implies that X ′ removes C. Otherwise, we have v ∈ {u j i , u k i , u ℓ i } ⊂ X ′ and X ′ removes C. Hence C is removed by X ′ . We apply this strategy until there is no edge backward without a vertex in X ′ . Further, let (u i j , u j i ) be an edge backward arc such that {u i j , u j i } ⊂ X. We set X ′ = X ∪ {h i } \ {u j i }. Let C be cycle containing u j i . If C contains the vertex backward arc (t i , h i ) then C is removed by the deletion of h i . Otherwise, C contains an edge backward arc and since every edge backward arc contains a vertex in X ′ , then C is removed by X ′ .

Let v be a vertex in X ′ such that v is not adjacent to a backward arc. By construction v is u j i vertex and thus, any cycle C containing v also contains an edge backward arc a. Since every edge backward arc contains a vertex in X ′ then X ′ \ {v} contains the vertex in a ∩ X ′ and thus X ′ \ {v} removes C. Hence, we can remove v from X ′ . Theorem 8. FVST is NP-complete on sparse tournaments.

Proof. Let G be a cubic graph and T be a sparse tournament resulting from Construction 2 along with the sparse ordering σ. We show that G contains a vertex cover of size c if and only if T has a solution for FVST of size c + |E(G)|.

Let S be a vertex cover of size c for G. We construct a solution X for FVST in T . For each vertex v i ∈ S, we set h i ∈ X. For each vertex v i ̸ ∈ S, let v j , v k and v ℓ be the three neighbours of v i . We set {u j i , u k i , u ℓ i } ⊂ X. Finally, for any edge v i v j such that {v i , v j } ⊂ S, we set u i j ∈ X. Let C be a cycle of T . If C contains only one backward arc that is a vertex backward arc (t i , h i ), then either v i ∈ S and C is removed by the deletion of h i or v i ̸ ∈ S and C is removed by the deletions of u j i , u k i and u ℓ i (where v j , v k and v ℓ are the neighbours of v i ). Otherwise, C contains an edge backward arc (u j i , u i j ) and since {u j i , u i j } ∩ X ̸ = ∅, C is removed by X. Hence X is a solution for FVST in T and we have |X| = c + |E(G)|.

Let X be a solution of size c + |E(G)| for FVST with respect to Lemma 13 property. We construct a vertex cover S for G. For each vertex backward arc (t i , h i ), if (t i , h i ) is not saturated then we set v i ∈ S i . Let v i v j be an edge of G. Since (u i j , u j i ) contains exactly one vertex in X, then at least one vertex backward arc among (t i , h i ) and (t j , h j ) is not saturated. Thus, either v i or v j belongs to S and v i v j is covered. Hence, we construct a vertex cover for G of size c.

Conclusion

In this paper, we studied a new parameter for tournaments, called degreewidth. We showed that it is NP-hard to decide if degreewidth is at most k, for some natural number k and we proceeded to design a 3-approximation for the degreewidth. One may ask if there is a PTAS for this problem. Then, we investigated sparse tournaments, i.e., tournaments with degreewidth one and developed a polynomial time algorithm to compute a sparse ordering. Is it possible to generalise this result by providing an FPT algorithm to compute the degreewidth? We also showed that FAST can be solved in polynomial time in sparse tournaments, matching with the known result that Arc-Disjoint Triangles Packing and Arc-Disjoint Cycle Packing are both polynomial in sparse tournaments [START_REF] Bessy | Packing arc-disjoint cycles in tournaments[END_REF]. Therefore, the question arise: can this parameter be used to provide an FPT algorithm for FAST in the general case? Furthermore, we showed an FPT algorithm for DS w.r.t degreewidth. Are there other domination problems e.g., perfect code, partial dominating set, or connected dominating set that is FPT w.r.t degreewidth? Lastly, we also can wonder if this parameter is useful for general digraphs.

2 .

 2 a) Example of a tournament with degreewidth one but fas (resp. fvs) |V (T )| (c) Example of a tournament with degreewidth one but cutwidth |V (T )|-1 Since the vertices are sorted by increasing in-degrees (values inside the vertices), this is an optimal ordering for the cutwidth.

Fig. 1

 1 Fig. 1 Link between degreewidth and other parameters. All the non-depicted arcs are forward.Similarly, a feedback vertex set (fvs) consists of a collection of vertices that, when removed from the digraph makes it acyclic. However, -unlike the feedback arc set -the link between feedback vertex set and degreewidth seems less clear; we can easily construct tournaments with low degreewidth and large fvs (see Figure1(a)) as well as large degreewidth and small fvs (see Figure1(b)).

2 backward 4 + 7m+11n 2 < 2 = W - 1 2 2 + 2 = W - 1 2 2 + 2 =

 2422122122 arcs between a and A \ {a}. By construction, there are |U ∪ Y ∪ D| = W +1 2 + 3m + 5n backward arcs between a and V (T ) \ A. Thus, we have d σ (a) ≤ 3W +1 W + 2m + 3n + 4. Let b be a vertex of B, there are at most |B|-1 backward arcs between b and B\{b}. By construction, there are at most |X| = 2n backward arcs between b and V (T ) \ B. Thus, we have d σ (b) ≤ W -1 2n < W + 2m + 3n + 4. Let c be a vertex of C, there are at most |C|-1 backward arcs between c and C \{c}. By construction, there are at most |X| = 2n backward arcs between c and V (T ) \ C. Thus, we have d σ (c) ≤ W -1 2n < W + 2m + 3n + 4. Let d be a vertex of D, there are at most |D|-1 W -1 4 + m+n 2 backward arcs between d and D \ {d}. By construction, there are |A ∪ U ∪ Y | = W +1 2 + 3m + 5n backward arcs between d and V (T ) \ D. Thus, the degreewidth of d with respect to σ is at most 3W +1 4

  for some variable x i of φ. There are at most |X|-1 = 2n-1 backward arcs between v and X \{v}. If v belongs to the true zone, then there are |C| = W backward arcs between v and C and none between v and B. If v belongs to the false zone, then there are |B| = W backward arcs between v and B and none between v and C. By construction there are |U | 2 = 2n backward arcs between v and U . Let

1 2

 1 we also reach a contradiction. Therefore, we have A ≺ σ D. Proof that A ≺ σ B and C ≺ σ D: Let a ∈ A be the rightmost vertex of A and b ∈ B be the leftmost vertex of B. Toward a contradiction, suppose that b ≺ σ a. If there is no vertex w ∈ U ∪Y between b and a, then by construction, we can exchange the positions of a and b without increasing the degreewidth of σ. Suppose there is a vertex w ∈ U ∪ Y such that b ≺ σ w ≺ σ a. Let B L = {b ′ | b ′ ∈ B, b ′ ≺ σ w} and B R = B \ B L . Since A is a regular tournament, we have |A|-backward arcs between a and A \ {a}. Since B L ≺ σ a, we have |B L | backward arcs between B L and a. By the previous item, we have a ≺ σ D and thus, there are D backward arcs between a and D. Hence, d σ (a) ≥ |A|-1 2

  Since we reach a contradiction, we have A ≺ σ B. By symmetry, we can use the same argument to show that C ≺ σ D. Proof that B ≺ σ C: Let b ∈ B be the rightmost vertex of B and c ∈ C be the leftmost vertex of C. Toward a contradiction, suppose that c ≺ σ b. If there is no variable vertex between c and b, then we can exchange the positions of c and b without increasing the degreewidth of σ. Suppose that there is a

1 2

 1 Now, since B is a regular tournament, there are |B|-backward arcs between B \ {b} and b. By construction, we have |C L | backward arcs between C L and b. So,

Lemma 4 .

 4 Let T be a sparse tournament of order n > 4 and σ be an ordering of its vertices. If σ is a sparse ordering, then for any vertex v such that d -(v) = i, the only possible positions of v in σ are {i, i + 1, i + 2} ∩ [n].

Figures 4 (

 4 Figures 4(b) and 4(c) (and Figures 4(e) and 4(f)) depict the orderings Π 1 (U 7 ) and Π 7 (U 7 ) (resp. Π(U 8 ) and Π 1,8 (U 8 )) of the tournament U 7 (resp. U 8 ). One can notice that these orderings are sparse and the subscript of Π indicates the vertex (or vertices) without a backward arc incident to it in this ordering. In the following, we prove that when n > 4 there are no other sparse orderings of U n . However, note that there are three possible sparse orderings of U 3 (namely, Π 1 (U 3 ) and Π 3 (U 3 ) defined previously, as well as Π 2 (U 3 ) := ⟨v 3 , v 2 , v 1 ⟩) and three sparse orderings of U 4 (namely, Π(U 4 ), Π 1,4 (U 4 ) as defined before, andΠ ′ (U 4 ) := ⟨v 2 , v 4 , v 1 , v 3 ⟩).In order to prove that there are no other sparse orderings of U n , we start by giving some properties on the position of the vertices; specifically, we refine the statement of Lemma 4 in the case where the tournament is U n .

Fig. 5

 5 Fig. 5 An example where X (b, a)quasi-dominates T . Non-depicted arcs are forward. The vertex a ′ is an outneighbour of a in X, and b ′ , b ′′ are inneighbours of b in T -X.

Fig. 6

 6 Fig. 6 Example of tournament T where X (b, a)-quasi-dominates T and X is (M ∪ {a}) ∩ X-sparse and T -X is (M ∪ {b}) \ X-sparse. Vertices of M are coloured orange.

14 else 15 a

 1415 , b ←the vertices such that X (b, a)-quasi-dominates T ; 16 return ( isUkMsparse(X,(M ∪ {a}) ∩ X) and isMsparse(T -X, (M ∪ {b}) \ X));

  First we show that Algorithm 2 runs in time O(n). As M has size at most n and computing |M | and |M \{v 1 , v k }| runs in time O(M ) and thus the total time is O(n). Let us now show that Algorithm 1 runs in time O(n 2 ). As N -(u k ) is of size at most n, then finding w (line 1) can be done in time O(n). Computing the in-degree of w costs O(n). The in-degree of u k is k -1 by definition. According to the master theorem, Algorithm 1 runs in time O(n 2 ). Let us now show that Algorithm 3 runs in time O(n 3 ). Computing min v∈V (T ) d -(v) and finding the vertices which minimises the in-degree runs in time O(n 2 ). The vertices (a, b) in Line 15 such that X (b, a)-quasi-dominates T can be computed during Algorithm 1 and thus it results in an empty cost. All the other operations runs in O(n 2 ) time. According to the master theorem of analysis of algorithm, this algorithm runs in time O(n 3 ).

Corollary 2 .

 2 The vertex set of a sparse tournament on n vertices can be decomposed into a sequence U n1 , U n2 , . . . , U n ℓ for some ℓ ≤ n such that eachT [U ni ] dominates or quasi-dominates T [ ∪ i<j≤ℓ U nj ] and i∈[ℓ] n i = n.5 Degreewidth as a parameter 5.1 Dominating set parameterized by degreewidth A set of vertices X of a directed graph G is a dominating set (DS) if for each vertex

Not to be confused with sparse tournaments that has an arc between every pair of vertices, hence, is not a sparse graph.

Acknowledgements

We would like to thank Frédéric Havet for pointing us a counter-example to the polynomial running-time algorithm in [25, Lemma 35.1, p.97].

when majority of this work was done. Jocelyn Thiebaut was supported by the CTU Global postdoc fellowship program.

Let us now prove that there are no two consecutive vertices ⟨v i , v i+1 ⟩ for each i ∈ [n -1]. By contradiction, consider a sparse ordering σ such that v i and v i+1 are consecutive. By definition of U n , the arc (v i+1 , v i ) is a backward arc. Suppose first that i > 1. Since σ is sparse, then the in-neighbours of v i (resp. v i+1 ) are exactly the vertices before v i (resp. v i+1 ). So the vertex v i-1 is necessarily between v i and v i+1 , yielding a contradiction.

Let us consider now the case i = 1. Note that if v 1 is not the first vertex, then v k for some k ≥ 3 is before v 1 , contradicting Lemma 4. Then v 3 is after v 2 , proving that d σ (v 2 ) ≥ 2, a contradiction. Theorem 4. For each integer n > 4 there are exactly two sparse orderings of U n . Specifically, if n is even, these two sparse orderings are Π(U n ) and Π 1,n (U n ); otherwise, the two sparse orderings are Π 1 (U n ) and Π n (U n ).

Proof. We prove the theorem by induction on the number of vertices. First, we show that Π 1 (U 5 ) and Π 5 (U 5 ) are the two only sparse orderings of U 5 . Using Lemma 5, we know that v 1 is either at position 1 or position 2 in any sparse ordering. Suppose the former. Lemma 5 forbids the vertex v 2 to be after v 1 , then the only possible vertex at position 2 is v 3 and the only possible remaining position for v 2 is the third one. Finally, we cannot have the pattern ⟨v 4 , v 5 ⟩ by Lemma 5, so the only possible sparse ordering of

Similarly, suppose now v 1 is at position 2. Then the first vertex is necessarily v 2 . Note that v 3 cannot be at position 3 since it would have two backward arcs (v 3 , v 2 ) and (v 4 , v 3 ). Then the only other option by Lemma 5 is v 4 . Then we necessarily obtain the ordering ⟨v 2 , v 1 , v 4 , v 3 , v 5 ⟩, that is Π 1 (U 5 ).

Similarly, we prove that Π(U 6 ) and Π 1,6 (U 6 ) are the two only sparse tournaments of U 6 . Let us suppose that v 1 is the first vertex. Then, as before v 3 is at position 2, and v 2 at position 3. Note that v 4 cannot be at position 4 since it would have two backward arcs (v 5 , v 4 ) and (v 4 , v 3 ). Then the last possible position for v 4 is 5, which leads to the ordering ⟨v

Finally, if we suppose that v 1 is at position 2, using the same arguments as for Π 1 (U 5 ) we directly obtain the ordering Π 1,6 (U 6 ).

Suppose now that U n respects the statement of the theorem, and let us prove that U n+1 does too. Let us first consider the case where n is even. Note that if we remove the vertex v n+1 from U n+1 , we obtain exactly U n . Now, since n is even, consider the ordering Π(U n ) on which we will insert v n+1 . By Lemma 5 we can only insert v n+1 at position n, and we obtain exactly Π n+1 (U n+1 ). If we now consider the ordering Π 1,n (U n ) on which we will also insert v n+1 , then by Lemma 5 we can only insert v n+1 at position n + 1, and we obtain exactly Π 1 (U n+1 ). This concludes the case where n is even.

Let us now suppose n odd. Similarly as before, note that if we remove the vertex v n+1 from U n+1 , we obtain exactly U n . Consider first the ordering Π n (U n ) on which we will insert v n+1 . By Lemma 5 we can only insert v n+1 at position n + 1, and we obtain exactly Π(U n+1 ). If we now consider the ordering Π 1 (U n ) Lemma 9. Let T be a tournament and X be a list of vertices satisfying the U -property. Then T [X] is the tournament U k .

Proof. We will prove by induction the following assertion: the subtournament T [{v 1 , . . . , v i }] is U i for any i ≥ 1. The assertion is true for i = 1. Suppose that it is true for i ≥ 1. Let us prove that it is true for i

Observation 4. Let T be a tournament and a list X = (v 1 , . . . , v k ) of vertices satisfying the U -property. Then v k has one in-neighbour in V (T ) \ X.

Proof. Since X satisfies the U -property, we have

Lemma 10. Let T be a tournament and a list X = (v 1 , . . . , v k ) of vertices satisfying the U -property. Let w be the vertex of N -(v k )\X. We denote (v 1 , . . . , v k , w) by X ′ .

-

T . Remark that in every case X is included in a U -sub-tournament dominating or quasi-dominating T .

Proof. We prove this lemma by induction on k the number of vertices of X. If k = n -1, then X ′ is a U -sub-tournament dominating T . Suppose now that the result is true for k + 1. We will prove that it is true for k.

Observe that by Lemma 9,

) -1 and we deduce that X ′ = (v 1 , . . . , v k , w) satisfies the U -property. Thus, by induction, X ′ is included in a U -sub-tournament dominating or quasi-dominating T .

Suppose that

That is, we show that the four conditions for quasi-domination holds. First, the arc (w, v k ) ∈ A(T ) and w ̸ ∈ X.

We now show the correctness of f . First, we show that f ((u i , v i )) ̸ = ∅ for every arc of B. For cases (a) to (c), f ((

Further, we show that for every arc (s, t) ∈ S, we have |f -1 ((s, t))| ≤ 1. If (s, t) has been assigned as a case (a), then (s, t) is a backward arc and f ((s, t)) = (s, t) and since it is not possible to assign a backward arc to another backward arc than itself, we have |f -1 ((s, t))| = 1. Note that if (s, t) is not a backward arc, then for any backward arc (u i , v i ), such that f ((u i , v i )) = (s, t), (s, t) is incident to (u i , v i ). Hence, we have either s = v i and t ∈ {x i , y i } (when (s, t) is incident to v i in cases (c) or (d)) or s ∈ {x i , y i } and t = u i (when (s, t) is incident to u i in cases (b) or (d)). Hence, (s, t) can be assigned by at most two different backward arcs and s is the head of one of them and t is the tail of one of them. Suppose that there exists a backward arc (u i , v i ) such that t = u i which is assigned to (s, t) and another backward arc (u j , v j ) such that s = v j which is also assigned to (s, t). Suppose that (u j , v j ) is assigned to (s, t) as a case (c), we then have s = v j and t = x j = u i . Since v i ≺ σ v j , (u i , v i ) is assigned before (u j , v j ), we have f -1 ((s = v j , t = x j = u i )) ̸ = ∅ when (u j , v j ) is assigned which is a contradiction. Now, suppose that (u j , v j ) is assigned to (s, t) as a case (d), we then have s = v j and t = y j = u i . As (u i , v i ) has been assigned to (v j , u i ), then v j is either x i or y i . Moreover, there is another backward arc (u ℓ , v ℓ ) such that f (u ℓ , v ℓ ) = (v j , u ℓ = x j ) since we are in case (d). As before v j is either x ℓ or y ℓ . Therefore, there are two cases: either we have the pattern ⟨v i , v ℓ , v j ⟩ either we have the pattern ⟨v ℓ , v i , v j ⟩. In the first case, (u i , v i ) is assigned to (v j = y i , t = u i ) as a case (d). Thus, there exists a backward arc leaving x i = v ℓ which contradicts that σ is sparse. In the second case, (u ℓ , v ℓ ) is assigned to (y ℓ = v j , u ℓ ) as a case (d). Hence, there exists a backward arc leaving x ℓ = v i which contradicts that σ is sparse. We can conclude that f is an injective function which implies that |B| ≤ |S|. Hence, |B| is a minimum feedback arc set.

Finally, since σ can be computed in time O(n 3 ) by Lemma 12, a solution of FAST for T can also be computed in polynomial time by taking the backward arcs of T in σ.

For FVST, we show that the problem is difficult to solve on sparse tournaments. Construction 2. Let G be a cubic graph with vertices {v 1 , . . . , v n }. We construct the following tournament T along with the sparse ordering σ.

-For every vertex v i , let N (v i ) = {v j , v k , v ℓ } be the neighbours of v i in G. We introduce the pattern p i =< h i , u j i , u k i , u ℓ i , t i , x 1 i , x 2 i , x 3 i >. -For every pair of vertices v i and v j such that i < j, we order σ such that p i ≺ σ p j . -Introduce the following backward arcs. For each vertex v i , construct the backward arc (t i , h i ) (vertex backward arc). For every edge v i v j such that i < j, construct the backward arc (u i j , u j i ) (edge backward arc). Any other arc is a forward arc.

Let T be a tournament and X be a solution for FVST. A backward arc (t, h) is said saturated by X (or simply saturated) if for every vertex x such that