Winning a Tournament by Any Means Necessary

1 Introduction

In a (cup) tournament, we have a set N of n players who enter the competition, but only one can be the winner. In each round, the players are paired-up to compete against each other. Losers are thrown away, while winners proceed to the next round, until only one lucky player is left. This is a standard form of competition in sports, popular culture, elections and decision making schemes. Significant attention has been given to tournaments from the viewpoints of both artificial intelligence and economics and operation research [Rosen, 1986; Tullock, 1980; Laslier, 1997]. In real life, we can often predict (with high success rate) the outcome, for every pair of players, of a match between them. Given such tentative information, the inherent highly competitive nature of a tournament makes it attractive for manipulators. Here, we focus on the combination (introduced by Kim and Williams [Kim and Williams, 2015]) of two common forms of manipulation. We present "obfuscation operations", combinatorial results, polynomial-time algorithms for special cases, and exact exponential-time algorithms for the general case.

To explain how a tournament is conducted and manipulated formally, we need the following definitions. By fixing a tournament we refer to a bijective labeling (by N) of the leaves of a full binary tree T with n leaves (where n is a power of 2). The labeling of the internal vertices of T is determined as follows. While we have an unlabelled vertex v with two labeled children x and y, we label v by the winner of a match between the players corresponding to the labels of x and y. The winner of the tournament is the player corresponding to the label of the root of T. Clearly, this process is a precise model for the execution of a tournament. The predictive information we have at hand is modeled by a digraph D with V (D) = N and where for every pair of players u, v ∈ N, either (u, v) ∈ A(D) (which means that u beats v) or (v, u) ∈ A(D) (which means that v beats u). Using terms from graph theory, D is called a tournament (not to be confused with the competition, also called a tournament).

It is natural to ask whether, given N, D and w ∈ N, there is a way to fix the tournament so that w wins. This problem, called TOURNAMENT FIXING (TF), was introduced by Vu et al. [Vu et al., 2009]. From a computational point of view, Aziz et al. [Aziz et al., 2014] showed that TF is NPhard, solvable in time O(2.83n ) and space O(1.76n ) (or time 4n+o(n) and polynomial space), and that parameterized by the feedback arc set number k of D, it is in XP (specifically, solvable in time O(n2k logn)). Later, Kim and Williams [Kim and Williams, 2015] gave an O(2n )-time and space algorithm for TF. These algorithms can also count the number of fixings that make w win. The parameter k has a natural interpretation as follows. In real world competitions, there is a ranking of players' strengths (e.g., think of Tennis rankings), so that a player of a certain rank is expected to beat players of a lower rank. Indeed, this assumption is the basis of probabilistic models that study tournaments (e.g., see [Stanton and Williams, 2011b]). The number of matches where we guess (before the competition begins) that a player of a certain rank will beat a player of higher rank is generally very small. This number is an upper bound on k, implying that k is generally significantly smaller than n. In light of this, it is reasonable to seek a fixed-parameter tractable (FPT) algorithm, i.e. an algorithm whose time complexity is f(k) · nc for some function f only of k and some constant c ≥ 0 independent of k. In particular, when f(k) = nO(1) , the algorithm runs in polynomial time. Using integer linear programming in fixed dimension, Ramanujan and Szeider [Ramanujan and Szeider, 2017] developed an FPT algorithm for TF that runs in time 2O(k2 log k)nO(1) . From the viewpoint of parameterized complexity, also Aronshtam et al. [Aronshtam et al., 2017] studied (several variants of) TF with appropriate parameterizations. For example, they studied the question of whether we can fix the tournament so that w wins at least k matches (but possibly not all matches). With respect to the parameter d, the maximum number of players that any player can beat, they obtained an FPT algorithm that runs in time d2d nO(1) .

In addition, TF received significant attention from a structural point of view-an array of works exhibited structural properties of D that guarantee that w wins [Kim et al., 2016; Kim and Williams, 2015; Stanton and Williams, 2011b; 2011a; Williams, 2010]. Let us review some of the results that are closer to our study (with emphasis on non-probabilistic structural statements), and refer the reader to the survey [Williams, 2016] for more information. Williams [Williams, 2010] studied the case where w is a king (resp. super king), that is, every player is either beaten by w or beaten by a player that is beaten by w (resp. logn players that are beaten by w). In particular, she showed that for a king w that beats at least half the players, there always exists a fixing that makes w the winner, while for a king w that beats less than half the players, there might not exist a fixing that makes w the winner. In addition, she showed that if w is a super king, then there exists a fixing that makes w win.

Later, Stanton and Williams [Stanton and Williams, 2011a] strengthened the work by Williams [Williams, 2010] with respect to her results for a probabilistic model, and by extending her condition that ensures that a king can always win. In a different work, Stanton and Williams [Stanton and Williams, 2011b] exhibited sufficient and necessary conditions that ensure that for any player w among the K players that have the largest out-degrees in D (for certain choices of K), there exists a fixing that makes w the winner. More recently, Kim and Williams [Kim and Williams, 2015] proved that TF is NP-hard even if w is a king that beats n/4 players, or if w is a so called 3-king (that is not as strong as a king) that beats half the players. They also provided a sufficient condition to ensure that a 3-king can win the tournament. Later, Kim et al. [Kim et al., 2016] further extended and generalized previous structural results, including the study of the power of 3kings. We remark that a certain argument in one of our proofs may be viewed in the terms of a king (see Section 5), but apart from this curiosity, the notions we introduce are incomparable to those of kings and of the K best players by [Stanton and Williams, 2011b] (see Section 4).

In addition, several studies present empirical results. For example, Mattei and Walsh [Mattei and Walsh, 2016] showed that although TF is NP-hard, real world soccer and tennis instances (English Premier League, the German Bundesliga, and the ATP World Tour) are easily solvable. Indeed, real world instances are generally structured, hinting at the relevance of appropriate parameterizations to capture these structures. Another empirical study on TF was conducted by Russell and Beek [Russell and van Beek, 2011], which focused on restrictions on the space of possible seedings. Here, the motivation is that real cup competitions often place restrictions to ensure fairness and wide geographic interest, which make the problem harder to solve in practice.

Kim and Williams [Kim and Williams, 2015] introduced a more general question, called BRIBERY TF (BTF). Given N, D, w ∈ N and ℓ ∈ N ∪ {0}, BTF asks if it is possible to reverse at most ℓ arcs in D (that is, change the outcome of at most ℓ matches) so that afterwards there is a way to fix the tournament that makes w wins. TF is the special case of BTF where ℓ = 0, which implies that BTF is NP-hard. Kim and Williams [Kim and Williams, 2015] proved that for any fixed ϵ > 0, BTF is NP-hard even if ℓ < (1 - ϵ) log2 n. On the other hand, they observed that if ℓ ≥ log2 n, then the input is a YES-instance.

Prior to [Kim and Williams, 2015], bribery has already been studied with respect to tournaments whose seeding is fixed in advance. The computational complexity of this problem is significantly simpler than that of TF. In particular, Russell and Walsh [Russell and Walsh, 2009] showed that this problem is solvable in polynomial time. In fact, this result was proved in a more general setting where we have a coalition (a set of players) such that all manipulations must involve a lose of one of its members. Additionally, Mattei et al. [Mattei et al., 2015] showed that even in a probabilistic model, where we want to make w have a nonzero probability of winning, the problem is still solvable in polynomial time.

Our contribution is fourfold. First, we present two "obfuscation operations", whose input is a solution, i.e. a set of at most ℓ arcs to reverse and a fixing of the tournament (with these arcs reversed). If the operation is applicable, it returns (in polynomial time) a different solution. These operations are relevant when: (i) the deceit in the current solution is too conspicuous; (ii) the current solution could not be realized (e.g., some player refused to be bribed). Moreover, we use these two operations as building blocks in our proofs.

Secondly, we present a combinatorial result, which states that there always exists a solution with all reversals incident to w and "elite players". Roughly speaking, given a feedback arc set K of D with k = |V (K)|, we partition V (D) \ V (K) into k + 1 modules. Each of these modules induces a DAG, and an elite club roughly refers to a set of players of "highest rank" in the topological order of each of these DAGs (the formal definition is more general and robust, see Definition 2). Our definition of an elite club in incomparable to the notions discussed earlier (see the explanation in Section 4).

Third, we give a closed formula (based on our combinatorial result) that resolves the special case of BTF where D is a DAG. More precisely, the formula is satisfied if and only if the input instance of BTF is a YES-instance. The formula can be verified in polynomial time. Moreover, its proof is constructive (the satisfaction of the formula indicates that a certain candidate to be a solution is indeed a solution). In addition, we generalize our formula to characterize all YESinstances also for the general case. Of course, the general characterization cannot be verified in polynomial time.

Finally, we present exact algorithms for the general case of BTF. (Recall that in its full generality, BTF is NPhard.) Specifically, we develop an algorithm that runs in time 2nnO(1) and has a polynomial space complexity (which improves upon the algorithm by Kim and Williams [Kim and Williams, 2015] in the special case of TF), as well as a parameterized algorithm that runs in time 2O(k2 log k)nO(1) , where k is the feedback arc set number of D. The latter algorithm implies that BTF is FPT parameterized by k alone.

2 Preliminaries

Denote [n] = {1, . . . , n}. Given a digraph D, denote its arcset and vertex-set by A(D) and V (D), respectively. Given U ⊆ V (D), by D[U] denote the subdigraph of D induced by U. Given R ⊆ A(D), denote Rrev = {(u, v) : (v, u) ∈ R}. Moreover, DR denotes the digraph obtained from D by reversing all arcs in R, that is, V (DR) = V (D) and A(DR) = (A(D) \ R) ∪ Rrev . We say that R is a feedback arc set of D if DR is a directed acyclic graph (DAG), i.e. DR has no directed cycle. By V (R) we denote the set of vertices incident to the arcs in R. The feedback arc set number of D is the minimum size of a feedback arc set of D.

A topological order of a DAG D is a total order < on V (D) such that for all u, v ∈ V (D), if u < v then (v, u) /∈ A(D). That is, if we denote V (D) = {v1, v2, . . . , vn} such that vi < vj whenever i < j, then each vertex vi can only have outgoing arcs into vertices of lower rank (i.e. larger index). We say that vi is the predecessor of vi+1, and vi+1 is the successor of vi, for all i ∈ {1, 2, . . . , n}. Note that if D is an acyclic tournament, then < is uniquely defined.

Given a tournament D and a feedback arc set K of D, the type of a vertex v ∈ V (D) \ V (K) is i ∈ {0, 1, . . . , k} if there are exactly i vertices u ∈ V (K) such that u < v with respect to the topological order < of DK (see Fig. 1).

Given a rooted tree T and v ∈ V (T), we let Tv denote the subtree of T rooted at v. Towards a reformulation of BTF, we need the concept of a binomial arborescence (see Fig. 2).

Definition 1. A binomial arborescence is defined recursively:

• A single node v is a binomial arborescence rooted at v.
• Given two vertex disjoint binomial arborescences of equal size, Tv rooted at v and Tu rooted at u, adding an arc from v to u results in a binomial arborescence rooted at v.

Given a tournament D, we say that a binomial arborescence T is spanning if V (T) = V (D). The proposition below gives rise to a graph theoretic interpretation of BTF.

Proposition 1 ([Williams, 2010]). For a tournament D with w ∈ V (D), there is a fixing of D that makes w win if and only if D has a spanning binomial arborescence T rooted at w.

In particular, if we have a fixing of D where w wins, then by taking all arcs in D corresponding to the matches that took place in the competition, we obtain a spanning binomial arborescence T rooted at w. On the other hand, having a spanning binomial arborescence T rooted at w, the tournament can be fixed so that w wins and all matches that take place correspond to the arcs in T (see [Williams, 2010]). Having Proposition 1 at hand, BTF is equivalent to the following question: Is there R ⊆ A(D) of size at most ℓ such that DR has a spanning binomial arborescence rooted at w? Unless written otherwise, we take this point of view.

Finally, we state (without proof) immediate properties of binomial arborescences.

Observation 1. Let T be a binomial arborescence on n ≥ 2 vertices. Then, for every vertex v ∈ V (T), it holds that Tv is a spanning binomial arborescence of D[V (Tv)] and in particular |V (Tv)| is a power of 2. Moreover, the root of T has exactly log n children, v1, v2, . . . , vlog n, with |V (Tvi )| = 2i-1 for all i ∈ {1, 2, . . . , log n}.

3 Obfuscation Operations

We give two operations to turn one solution into another. In each operation, we have a tournament D, a subset R ⊆ A(D) of size at most ℓ, and a spanning binomial arborscence T of DR rooted at w. Without loss of generality, suppose Rrev = A(T) \A(D). We say that an operation is valid if it returns a subset R′ ⊆ A(D) of size at most ℓ, and a spanning binomial arborscence T ′ of DR′ rooted at w.

Subtree clean-up. Our first operation is called "subtree clean-up" (see Fig. 3). We say that this operation is applicable if there exists a vertex v ∈ V (T) \ {w} such that A(Tv) ∩Rrev ̸= ∅. Given such a vertex v ∈ V (T ) \ {w}, the operation is performed as follows.

First, since |V (Tv)| is a power of 2 (see Observation 1), we have that D[V (Tv)] admits a spanning binomial arborescence T ′u , rooted at some vertex u. To see this, arbitrarily fix a tournament on D[V (Tv)], conduct the competition, and let T ′u be the spanning binomial arborescence obtained by taking all arcs of D[V (Tv)] that correspond to the matches that took place. Note that the root u of T ′u might be v itself. However, T ′u ̸= Tv because T ′u is a subtree of D while A(Tv) ∩Rrev ̸= ∅ (which means that Tv is not a subtree of D). Let p be the parent of v in T (since v ̸= w, this parent exists). Now, if (p, u) ∈ A(D) then define R′ = R\A(Tv)rev , and otherwise (if (u, p) ∈ A(D)) define R′ = (R \ A(Tv)rev ) ∪ {(u, p)}. We define T ′ from T as follows: remove the tree Tv and the arc (p, v), and then add the tree T ′u and the arc (p, u).

Because Tv is a spanning binomial arborescence of DR[V (Tv)] (see Observation 1), we have that T ′u is isomorphic to Tv. Having this observation in mind, one can easily verify that T ′ is a spanning binomial arborescence of DR′ rooted at w. Moreover, |R′ | ≤ |(R \ A(Tv)rev ) ∪ {(u, p)}| ≤ |R| - |R ∩ A(Tv)rev | + 1 ≤ |R|. Thus, the validity of our operation follows.

Lemma 1. The subtree clean-up operation is valid.

Cyclic shift. Our second operation is called "cyclic shift" (see Fig. 4), where we assume that we are given a feedback arc set K of D with |V (K)| = k, and the topological order < of DK . We say that a directed subpath of T, denoted by P = p1 → p2 → · · · → pq, enables a cyclic shift if p1, p2, . . . , pq /∈ V (K) ∪ {w}

1. are vertices of the same type t ∈ {0, 1, . . . , k},
2. which are consecutive (that is, pi is the predecessor of pi+1 for all i ∈ {1, 2, . . . , q - 1}), and
3. the predecessor of p1 exists, it is not the parent of p1 in T, and it is also of type t.

We say that the cyclic shift operation is applicable if we have a directed subpath of T that enables a shift. Given such a subpath P = p1 → p2 → · · · → pq, the operation is performed as follows. Let p0 denote the predecessor of p1. Then, as the name of the operation suggests, we define T ′ from T as follows: for all i ∈ {0, 1, . . . , q}, replace the vertex pi by the vertex p(i-1)mod(q+1). Denote R′ = (A(T ′ ) \ A(D))rev . We now argue why this operation is valid.

Lemma 2 (*). 1 The cyclic shift operation is valid.

4 Combinatorial Result

In this section, we show that if the input instance of BTF is a YES-instance, then it admits a solution with two very specific properties. Apart from being a combinatorial result of independent interest, it is also useful practically as it significantly shrinks our search space. Only the second property assumes the presence of a feedback arc set K. If one is interested only in the first property, s/he can set K = A(D), and otherwise K can be obtained by either a polynomial-time approximation scheme (PTAS) [Kenyon-Mathieu and Schudy, 2007], or an 2O(√k)nO(1) -time parameterized algorithm [Karpinski and Schudy, 2010; Feige, 2009].

To formulate the second property, we introduce the following definition (examples are given below).

Definition 2. Let D be a tournament with a feedback arc set K. Let < be the topological order of DK . A set C ⊆ V (D) is an elite club if for all types i ∈ {0, . . . , |V (K)|}, there do not exist two vertices u, v of type i such that u < v, u /∈ C and v ∈ C. That is, if a vertex v of type i belongs to C, then all vertices u of type i that beat v also belong to C.

For w ∈ V (D), an elite club C is a w-elite club if (v, w) ∈ A(D) for all v ∈ C. That is, all members of C beat w.

For example, in Fig. 1, C1 = {v1, v3, v4, v5, v13, v14, v15, v18} is an elite club, while C2 = {v1, v3, v4, v6, v13, v14, v15, v18} is not since it contains v6 but not its predecessor v5 that belongs to the same type. It is easy to see that our notion of an elite club is incomparable to both the notion of kings and the best players defined by [Stanton and Williams, 2011b]. For example, a vertex v last of its type is a king if it beats, say, a vertex that beats any other vertex, and it is "likely to be" a best player if it belongs to one of the first types, but it belongs to an elite club C only if all vertices of the same type as v belong to C. Similarly, a vertex in an elite club (even if it is first of its type) can be neither a king nor a best player.

1 Due to lack of space, proofs of results marked by * are omitted.

Our main combinatorial result says that if there is a way to make w win, then there is also such a way where all matches necessary to alter involve w itself. Moreover, it further says that all of the other players that are involved in these matches belong to a group of "top players" (among those of each type). We think these two findings are of philosophical interest as well. Formally, this is stated as follows.

Theorem 1 (*). Let (D, w, ℓ) be a YES-instance of BTF. Let K be a feedback arc set of D with |V (K)| = k, and let < be the topological order of DK . Then, there exists R ⊆ A(D) with |R| ≤ ℓ and a spanning binomial arborscence T of DR rooted at w, which satisfy both properties below.

1. Every arc in R has w as an endpoint.
2. There exists a w-elite club C of size at most ℓ such that every arc in R has an endpoint in C.

5 Characterization of YES-Instances

In this section, we present two (related) characterizations of YES-instances, along with one implication. First, based on Theorem 1 and Observation 1, we present a closed formula that resolves the special case of BTF where D is a DAG. To this end, we need the following definition.

Definition 3. Let D be a tournament. The victory count of a vertex v ∈ V (D), denoted by victory(v), is defined by

That is, victory(v) is the number of players beaten by v.

We are now ready to state our formula. While the statement is existential, the proof is constructive and implies how a solution, if one exists, can be found.

Theorem 2. Let (D,w, ℓ) be an instance of BTF where D is a DAG. Then, (D,w, ℓ) is a YES-instance if and only if the expression [victory(w) ≥ n 2ℓ - 1] is true. In case the expression is true, a solution can be found in polynomial time.

Proof sketch. In one direction, suppose that victory(w) ≥ n 2ℓ - 1 is true. Let S be a set of exactly n 2ℓ - 1 vertices beaten by w. Arbitrarily partition S into logn - ℓ sets, U1, . . . ,Ulogn-ℓ, such that |Ui| = 2i-1 for all i ∈ {1, . . . , logn-ℓ}. Since ∑logn-ℓ i=1 2i-1 = n 2ℓ -1, this is possible. Moreover, arbitrarily partition V (D) \ (U ∪ {w}) into ℓ sets, Ulogn-ℓ+1, . . . ,Ulogn, such that |Ui| = 2i-1 for all i ∈ {log n-ℓ+1, . . . , log n}. Now, for all i ∈ {1, . . . , log n}, fix a tournament (competition) for D[Ui], and let Ti denote the corresponding spanning binomial arborescence of D[Ui] rooted at some vertex wi. Define T by V (T) = V (T1) ∪ . . . ∪ V (Tlog n) ∪ {w} and A(T ) = A(T1) ∪ . . . ∪ A(Tlogn)∪{(w,wi) : i ∈ {1, . . . , logn}}. Moreover, define R = {(wi,w) ∈ A(D) : i ∈ {logn - ℓ + 1, . . . , logn}}. Then, |R| ≤ ℓ, and it is easy to verify that T is a spanning binomial arborescence of DR rooted at w. The proof also indicates how to construct a solution in polynomial time.

In the other direction, suppose that (D,w, ℓ) is a YESinstance. Let (R, T) be a solution that satisfies property 1 in Theorem 1. Let X be the set of children v of w in T such that (w, v) ∈ A(D), and denote U = ⋃v∈X V (Tv). Since |R| ≤ ℓ, we have that |X| ≥ logn - ℓ. Thus, by Observation 1, |U| = ∑v∈X |V (Tv)| ≥ ∑logn-ℓ i=1 2i-1 = n 2ℓ - 1. Moreover, since (R, T) satisfies property 1, we have that A(Tv) ∩Rrev = ∅ for all v ∈ X. Thus, since (w, v) ∈ A(D) for all v ∈ X and D is a DAG, we have that w beats all the vertices in U.

In our proof of the forward direction above, it can be shown that w is made a king by reversing ℓ arcs. The spirit of the proof of Theorem 2 is not limited to the special case of DAGs. Indeed, we have a characterization of YES-instances also for general tournaments. However, this characterization is not nice in the sense that it cannot be verified in polynomial time. Nevertheless, we find it of theoretical interest, and it will be used later. In this context, recall that BTF is NP-hard even when ℓ = 0, and hence we do not expect it to admit an easy to verify characterization.

Theorem 3. Let (D,w, ℓ) be an instance of BTF. Then, (D,w, ℓ) is a YES-instance if and only if there exists U ⊆ V (D) of size exactly n 2ℓ - 1 so that there is a fixing of D[U ∪ {w}] that makes w win. Given such U with its fixing, a solution can be found in polynomial time.

Proof sketch. In one direction, suppose that there exists U ⊆ V (D) of size exactly n 2ℓ - 1 so that there is a fixing of D[U ∪ {w}] that makes w win, and let T ′ be the corresponding binomial arborescence of D[U ∪ {w}] rooted at w. Arbitrarily partition V (D) \ (U ∪ {w}) into ℓ sets, Ulogn-ℓ+1, . . . ,Ulogn, such that |Ui| = 2i-1 for all i ∈ {logn - ℓ + 1, . . . , logn}. For all i ∈ {logn - ℓ + 1, . . . , logn}, fix a tournament (competition) for D[Ui], and let Ti denote the corresponding spanning binomial arborescence of D[Ui] rooted at some vertex wi. Define T by V (T) = V (Tlogn-ℓ+1) ∪ . . . ∪ V (Tlogn) ∪ V (T ′ ) and A(T) = A(Tlogn-ℓ+1) ∪ . . . ∪ A(Tlogn) ∪ {(w,wi) : i ∈ {logn - ℓ + 1, . . . , logn}} ∪ A(T ′ ). Moreover, define R = {(wi,w) ∈ A(D) : i ∈ {logn - ℓ + 1, . . . , logn}}. Similarly to the proof of Theorem 2, the claim follows.

In the other direction, suppose that (D,w, ℓ) is a YESinstance. Let (R, T) be a solution that satisfies property 1 in Theorem 1. Let X′ be the set of children v of w in T such that (w, v) ∈ A(D). Since |R| ≤ ℓ, we have that |X′ | ≥ logn - ℓ, and we denote by X some subset of X′ of size exactly log n-ℓ. Order X = {x1, . . . , xlog n-ℓ} such that |V (Txi )| ≤ |V (Txi+1 )| for all i ∈ {1, . . . , log n-ℓ-1}. Since (R, T) satisfies property 1, we know that Txi is a spanning binomial arborescence of D[V (Txi )] for all i ∈ {1, . . . , log n - ℓ}. By Observation 1, it can be verified that there exists a subtree T ′xi of Txi on exactly 2i-1 vertices that is a spanning binomial arborescence of D[V (T ′xi )] rooted at xi (the idea is to truncate the subtrees of the children of xi that are largest). Now, denote U = V (T ′x1 ) ∪ . . . ∪ V (T ′xlog n-ℓ ). Observe that |U| = ∑logn-ℓ i=1 |V (T ′xi )| = ∑logn-ℓ i=1 2i-1 = n 2ℓ -1. Thus, by taking all the arborescences T ′xi and adding the arcs (w, xi) (which belong to A(D) by our choice of X), we exhibit a spanning binomial arborescence of D[U ∪ {w}] that is rooted at w.

In our proof of the forward direction above, it can be shown that w is not necessarily made a king by reversing ℓ arcs. As a corollary of Theorem 3, we have the following one-way statement (which is constructive).

Theorem 4. Let (D,w, ℓ) be an instance of BTF. If victory(w) ≥ n 2ℓ - 1, then (D,w, ℓ) is a YES-instance. In this case, a solution can be found in polynomial time.

6 Exact Algorithms

Our exact algorithms are based on translating the characterization in Theorem 3 into the language of spanning binomial arborscences. To this end, we introduce a new definition (see Fig. 5). The validity of the sizes mentioned in this definition follows from Observation 1.

Definition 4. Let ℓ ∈ N. Let T be a binomial arborescence of size n with logn ≥ ℓ. Let the children of its root r be vi, i ∈ [log n], where |V (Tvi )| = 2i-1 for all i ∈ {1, . . . , log n}. An ℓ-removed binomial arborescence T ′ of size n is the digraph obtained from T by deleting the arcs (r, vi) for all i ∈ {log n-ℓ+1, . . . , log n}. The vertex r is the root of T ′ . 2

Note that up to isomorphism, an ℓ-removed binomial arborescence of size n is unique. We now give the promised translation of Theorem 3.

Lemma 3. Let (D,w, ℓ) be an instance of BTF. Then, (D, w, ℓ) is a YES-instance if and only if D contains a spanning ℓ-removed binomial arborescence T rooted at w.

Proof sketch. In one direction, suppose that D contains a spanning ℓ-removed binomial arborescence T rooted at w. Let T ′ denote the tree of T that is rooted at w. Then, |V (T ′ ) \ {w}| = n - 1 - ∑log n i=logn-ℓ+1 2i-1 = n 2ℓ - 1 (by Observation 1) and T ′ is a spanning binomial arborescence of D[V (T ′ )] rooted at w. Denoting U = V (T ′ ) \ {w}, the claim follows from the reverse direction of Theorem 3.

In the other direction, suppose that (D,w, ℓ) is a YESinstance. By the forward direction of Theorem 3, there exists U ⊆ V (D) of size exactly n 2ℓ - 1 so that there is a fixing of D[U ∪{w}] that makes w win. Let T ′ be a spanning binomial arborescence of D[U ∪{w}] rooted at w. Arbitrarily partition V (D) \ (U ∪ {w}) into ℓ sets, Ulogn-ℓ+1, . . . ,Ulogn, such that |Ui| = 2i-1 for all i ∈ {logn-ℓ+1, . . . , logn}. For all i ∈ {log n-ℓ+1, . . . , log n}, fix a tournament (competition) for D[Ui], and let Ti denote the corresponding spanning binomial arborescence of D[Ui] rooted at some vertex wi. Define T by V (T ) = V (Tlog n-ℓ+1) ∪ . . . ∪ V (Tlog n) ∪ V (T ′ ) and A(T) = A(Tlogn-ℓ+1) ∪ . . . ∪ A(Tlogn) ∪ A(T ′ ), and let w be its root. Then, it is easy to verify that T is a spanning ℓ-removed binomial arborescence of D rooted at w.

2 Although T ′ contains ℓ+1 vertices of in-degree 0, there is only one vertex that we define as the root.

Towards the presentation of our first algorithm, we show how to detect ℓ-removed binomial arborescences.

Lemma 4. Let D be a digraph, w ∈ V (D), and ℓ ∈ N. We can decide in time 2nnO(1) and polynomial space if D contains a spanning ℓ-removed binomial arborescence T rooted at w. If the answer is positive, we output T.

Proof sketch. Amini et al. [Amini et al., 2012] proved the following result. Suppose that we have two digraphs, D on n vertices and H on k vertices, such that the treewidth of the underlying undirected graph of H is t. Moreover, suppose that each vertex in D has a color from a set of k colors. Then, it can be decided in time 2k nt+O(1) and polynomial space if D has a colorful subgraph isomorphic to H. This algorithm can be immediately adapted to also solve the case where each digraph among D and H has a distinguished vertex, say, d and h, so that the isomorphism must match d and h. In our setting, H is the (unique) ℓ-removed binomial arborescence T on n vertices (that is, k = n), whose underlying undirected graph is a forest and hence has treewidth 1. The coloring is simply the identity function (that is, every vertex in D gets a unique color), d = w and h is the root of T . As the algorithm in [Amini et al., 2012] also outputs a copy of H in D (if one exists) in the same running time bound, the correctness of our lemma follows.

Having Lemmata 3 and 4, we are ready to present our exponential-time algorithm.

Theorem 5. BTF can be solved in time 2nnO(1) and polynomial space. In the case of a YES-instance, a solution can be found in the same running time bound.

Proof sketch. Given an instance (D,w, ℓ) of BTF, call the algorithm in Lemma 4 to decide if D contains an ℓ-removed binomial arborescence T ′ of size n rooted at w. If the answer is negative, return NO. Else, let T ′ be the output. Define T as the binomial arborescence obtained from T ′ by adding arcs from w to all other vertices in T ′ of in-degree 0. Moreover, define R = (A(T )\A(D))rev , and observe that |R| ≤ ℓ. The correctness of the algorithm then follows from Lemma 3.

Slight modification of the algorithm in [Ramanujan and Szeider, 2017], which detects if D has a spanning binomial arborescence rooted at w, proves the following.

Lemma 5 (*). Let D be a tournament with feedback arc set number k, w ∈ V (D) and ℓ ∈ N. We can decide in time 2O(k2 log k)nO(1) and polynomial space whether D contains an ℓ-removed binomial arborescence T of size n rooted at w. If the answer is positive, we output T .

Replacing Lemma 4 by Lemma 5 proves the following.

Theorem 6. BTF can be solved in time 2O(k2 log k)nO(1) and polynomial space, where k is the feedback arc set number of the input tournament. In case of a YES-instance, a solution can be found in the same running time bound.

7 Conclusion

In this paper, we studied BTF and gave combinatorial results, polynomial-time algorithms for special cases, and exact exponential-time algorithms for the general case. One of our results imply that the problem is FPT parameterized by k, the size of a feedback arc set of the input tournaments. A natural question, therefore, is whether the problem admits a polynomial kernel. Another open question is whether BTF (or even TOURNAMENT FIXING) is FPT when parameterized by the size of a feedback vertex set of the input tournament.

Acknowledgements

We would like to thank anonymous referees for valuable comments that helped improve the article.