# rigging_nearly_acyclic_tournaments_is_fixedparameter_tractable__10eddda0.pdf

Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable

M. S. Ramanujan and Stefan Szeider Algorithms and Complexity Group, TU Wien, Vienna, Austria [ramanujan,sz]@ac.tuwien.ac.at

Single-elimination tournaments (or knockout tournaments) are a popular format in sports competitions that is also widely used for decision making and elections. In this paper we study the algorithmic problem of manipulating the outcome of a tournament. More specifically, we study the problem of finding a seeding of the players such that a certain player wins the resulting tournament. The problem is known to be NP-hard in general. In this paper we present an algorithm for this problem that exploits structural restrictions on the tournament. More specifically, we establish that the problem is fixed-parameter tractable when parameterized by the size of a smallest feedback arc set of the tournament (interpreting the tournament as an oriented complete graph). This is a natural parameter because most problems on tournaments (including this one) are either trivial or easily solvable on acyclic tournaments, leading to the question what about nearly acyclic tournaments or tournaments with a small feedback arc set? Our result significantly improves upon a recent algorithm by Aziz et al. (2014) whose running time is bounded by an exponential function where the size of a smallest feedback arc set appears in the exponent and the base is the number of players.

Introduction Single-elimination tournaments, also known as knockout tournaments, are a popular format in sports competitions. It is used, for instance, at the Wimbledon tennis tournament and is widely applied in decision making and elections. As a result, the study of manipulating the results of knockout tournaments in various ways has received a lot of attention. In the TOURNAMENT FIXING PROBLEM (TFP), we are given the results of a round-robin tournament in the form of a tournament graph on n vertices, and a special player. The objective is to decide whether there is a seeding of the n players such that the special player is the winner of the resulting knockout tournament, given the same match outcomes between each pair of players. Aziz et al. (2014) showed that this problem is NP-hard in general while there are several results (Vassilevska Williams 2010; Stanton and Vassilevska Williams 2011; Kim and Vassilevska Williams 2015; Kim, Suksompong, and Vassilevska Williams 2016) identifying certain structural properties of the input tournament which guarantee that the required

Copyright c 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

seeding exists. We take the search for tractable instances of this problem in a different direction by studying the parameterized complexity of this problem. A parameterized problem P is a problem whose instances are tuples (I, k), where k N is called the parameter. The central notion of tractability in parameterized complexity is that of fixed parameter tractability. We say that a parameterized problem is fixed parameter tractable (FPT in short) if it can be solved by an algorithm which runs in time f(k) |I|O(1) for some computable function f; algorithms with running time of this form are called FPT algorithms. We refer the reader to other sources (Downey and Fellows 2013; Flum and Grohe 2006; Cygan et al. 2015) for an in-depth introduction into parameterized complexity. Numerous graph problems, when studied in the parameterized complexity setting with parameter k, turn out to be easily solvable in time nf(k) for some function f and the main goal in these situations is to achieve an FPT running time. However, this is not true in the case of graph layout problems where the goal is to compute a permutation of the vertex set which optimizes an objective function. Even on tournaments, an algorithm with running time nf(k) for some of these problems is very non-trivial and highly technical (see, e.g., Fradkin and Seymour 2013). The TFP problem is yet another graph layout problem where it is not at all obvious how one would go about designing even an algorithm that runs in time nf(k) where k is the size of the smallest feedback arc set in the tournament. Recently, Aziz et al. (2014) gave a clever dynamic programming algorithm with this running time, which relies on the bounded index of a certain equivalence relation induced by the feedback arc set on the set of players. In this paper, we show that the TFP problem is in fact fixed-parameter tractable parameterized by the size of the smallest feedback arc set by proving the following theorem.

Theorem 1. The TOURNAMENT FIXING PROBLEM can be solved in time 2O(k2 log k)n O(1) on tournaments of size n with a feedback arc set of size k.

This theorem implies that when the given tournament has a feedback arc set of size k, where k2 log k = O(log n) then it can be decided in polynomial time whether the tournament can be fixed to make a given player win. Our algorithm relies on a combination of certain new structural properties of

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

knockout tournaments with a small feedback arc set and an appropriate decomposition of arborescences. We believe that the structural results proved in this paper will have applications in further fixed-parameter algorithms for this problem.

Related Work The computational problem of manipulation knockout tournaments was first stated by Vu, Altman, and Shoham (2009) and has received a lot of attention (Kim, Suksompong, and Vassilevska Williams 2016; Kim and Vassilevska Williams 2015; Aziz et al. 2014; Stanton and Vassilevska Williams 2011; Vassilevska Williams 2010). Over recent years, the framework of fixed-parameter algorithms and parameterized complexity has been shown adequate and suitable for problems in computational social choice which includes questions related to tournaments and manipulations (Betzler et al. 2012; Lindner and Rothe 2008). Fixed-parameter tractability results for voting manipulations have recently been given by Hemaspaandra, Lavaee, and Menton (2016). Somewhat related is the computational problem of controlling candidates in elections, whose parameterzed complexity was recently studied in the AI context (Chen et al. 2015). Several other recent parameterized complexity results on manipulations of elections and rankings include (Yang 2014; Dey, Misra, and Narahari 2015; Bevern et al. 2016).

Preliminaries We begin by recalling the definition of seedings of a tournament. Let D be a round robin tournament on n players. That is, for every pair of players, exactly one is picked to be the winner of the match between them (depicted in D by an arc from the winner to the loser). A knockout tournament of D is defined by a binary tree T with n leaves L(T) and a bijective function S : V (D) L(T) called the seeding, mapping the n players to the n leaves. Then the winner of the knockout tournament corresponding to this seeding is determined recursively: the winner at a leaf l is the player j with l = S(j), and the winner of the subtree rooted at a node v is the winner of the match between the winners of the two subtournaments rooted at the children of v. Binomial arborescences. An arborescence is a rooted directed tree such that all arcs are directed away from the root. Definition 1 (see also Vassilevska Williams 2010). Let D be a tournament. A binomial arborescence T rooted at a V (D) is defined as follows. a single node a is a binomial arborescence rooted at a, if |V (T)| = 2i for some i > 0, then T is a binomial arborescence if a has a child b such that if Tb is the subarborescence of T rooted at b and Ta = T \ Tb, then Ta and Tb are 2i 1-node binomial arborescences rooted at a and b respectively. If V (T) = V (D), then we say that T is a spanning binomial arborescence of D. In the rest of the paper, we will refer to a spanning binomial arborescence simply as an s.b.a. The relevance of binomial arborescences comes from the following statement. Proposition 1 (Vassilevska Williams 2010). Let D be a tournament with a special vertex v V (D). Then, there is a

seeding of the vertices in D such that the resulting knockout tournament is won by v if and only if D has an s.b.a rooted at v .

Let T be a (not necessarily binomial) arborescence. For a vertex u V (T), we denote by Child T (u) the set of children of u in T, by Desc T (u) the set of descendants of u in T and by Ansc T (u) the set of ancestors of u in T. Note that u Desc T (u) Ansc T (u). Observe that if T is an s.b.a of D, then for every v V (T), |Desc(v)| = 2i for some i [log n] {0} and v is the winner of a subtournament played by the players in Desc(v). For an arborescence T, we say that another arborescence T is a leaf-subtree of T if T is the subtree of T induced on the set Desc(v) for some v V (T). We will use the terms vertex and player interchangeably. ILP-feasibility. We will use as a subroutine the well-known FPT algorithm for the ILP-FEASIBILITY problem. The ILPFEASIBILITY problem is defined as follows. The input is a pair of matrices A Zm p and b Zm 1 and the objective is to check whether there exists a vector x Zp 1 satisfying the m inequalities, that is, A x b.

Proposition 2 (Lenstra and Jr. 1983, Kannan 1987, Frank and Tardos 1987). ILP-FEASIBILITY can be solved using O(p2.5p+o(p) L) arithmetic operations and space polynomial in L, where L is the number of bits in the input and p is the number of variables.

Lemma 1. For every k, n N where k n, (log n)k (4k log k)k + n2.

The FPT algorithm for TFP Definition 2. Let D be a tournament with a special player v . Let F A(D) be a smallest feedback arc set of D and let π : [n] V (D) be the linear ordering of the players in decreasing order of strength obtained by flipping the arcs in F. In this ordering, player u appears before player v if and only if (u, v) is an arc. Then, we say that π witnesses F. We call the vertices in {v } V (F), affected vertices and denote this set by AF .

We now define the notion of a permutation γ of X V (D) respecting the permutation π witnessing F. Essentially, we say that γ respects π if the vertices of X appear in the same order (relative to each other) in γ as they do in π. The formal definition follows.

Definition 3. Let D be a tournament and X V (D). Let π : [n] V (D) be a linear ordering of V (D). Let γ : [|X|] X be an ordering of the vertices in X such that for every 1 i < j |X|, π 1(γ(i)) < π 1(γ(j)). Then, we say that γ is an ordering of X that respects π.

We will now define a type function that partitions the vertices in V (D)\AF into at most |AF |+1 partitions using the vertices in AF as breakpoints . We first define the set Types = [|AF | + 1] {AF }.

Definition 4. Let D be a tournament with a special player v . Let F A(D) be a smallest feedback arc set of D and let π : [n] V (D) be the linear ordering witnessing F. Let γ : [|AF |] AF be the ordering of AF that respects

τ 1(2) τ 1(3) τ 1(4) τ 1(5) τ 1(6)

Figure 1: An illustration of the partition of the vertices of D induced by the vertices in AF .

π. We define the type function τ π γ : V (D) Types as follows. For every v AF , τ π γ (v) = v. For every v V (D) \ AF , τ π γ (v) = i where i is the smallest index in [|AF |] such that π(v) < π(γ(i)). If there is no such index, that is, π(v) > π(γ(|AF |)), then we set τ π γ (v) = |AF | + 1. For each i Types, we denote by Pi(τ π γ ) the set of vertices in the pre-image of i under τ π γ . For an example of the way the type function τ π γ partitions V (D) \ AF , see Figure 1. When the permutations π and γ are clear from the context, we will simply refer to τ π γ as τ. When τ is clear from the context, we say that a vertex v has type τ(v) without explicitly referring to τ. Note that for some i [|AF | + 1], the set τ 1(i) could be empty (see Figure 1). We now observe that vertices in the same type have essentially the same behaviour with respect to every vertex of a different type in the graph. Lemma 2. Let τ be the type function as described earlier. For all i Types, and distinct vertices u, v τ 1(i), for any vertex w V (D) such that τ(u) = τ(w), w beats u if and only if w beats v. Motivated by the above lemma, for every u V (D), we define the set Types (u) as the set τ(u) {i Types \ AF | v τ 1(i), (u, v) A(D)}. That is Types (u) is τ(u) plus the set of those types in Types \ AF whose preimage-elements are all beaten by u which by the above lemma also means precisely those types in Types\AF which have at least one element which appears after u in the ordering π. We denote by Types<(u) the set Types \ Types (u). For a set Z V (D), we say that a vertex v Z is the strongest vertex of type τ(v) in Z if v beats every other vertex w Z such that τ(w) = τ(v). Similarly, we say that a vertex v Z is the weakest vertex of type τ(v) in Z if v is beaten by every other vertex w Z such that τ(w) = τ(v). If there is no u, v Z such that (u, v) F, then the subtournament D[Z] induced on D is acyclic and we have a natural notion of the strongest vertex in Z. This is simply the vertex of Z which beats every other vertex in Z. Let Z Z be a set of size ℓsuch that τ(u) = τ(v) = i for every u, v Z . We say that Z is the set of the strongest ℓvertices of type τ(u) in Z if there is no vertex w Z \ Z such that τ(w) = i and w beats a vertex in Z . Similarly, we say that Z is the set of the weakest ℓvertices of type τ(u) in Z if there is no vertex w Z \ Z such that τ(w) = i and w is beaten by a vertex in Z . We now show that the fact that the types themselves have a natural linear ordering is of great consequence.

Lemma 3. Let D be a tournament with a special player v , F A(D) a smallest feedback arc set of D and let π, γ, τ be as defined earlier. Then, the following statements hold.

For any u V (D) and Z

i Types (u) τ 1(i) such

that |Z| = 2j for some j [log n], let v be the strongest vertex of type τ(u) in Z. Then, there is a binomial arborescence rooted at v and spanning the set Z. Let Z0, Z1, . . . , Zℓbe disjoint non-empty sets of vertices such that ℓ j=0 |Zj| = 2p for some p [log n]. Let T1, . . . , Tℓbe binomial arborescences such that for each j [ℓ], Tj is rooted at rj and spans Zj. Suppose that there is no (u, v) F such that u, v Z0 and the strongest vertex q in Z0 beats rj for every j [ℓ]. Then, any binomial arborescence spanning the set Z and containing the binomial arborescences T1, . . . , Tℓas leaf-subtrees, must be rooted at q.

Proof. For the first statement, observe that by the definition of π, AF , γ and hence τ, along with the set Types (u), the vertex v beats every other vertex in the set Z. Hence, v wins every tournament played on the vertices in Z, implying that there is a binomial arborescence rooted at v and spanning the set Z (Proposition 1). For the second statement, suppose that there is such a binomial arborescence T which is not rooted at q. Let u Z be such that (u, q) A(T ). It cannot be the case that q V (Tj) \ {rj} for any j [ℓ] since by our assumption, Tj is required to be a leaf-subtree of T . Hence, the only remaining vertices of Z are the vertices in Z0 and the vertices r1, . . . , rℓ, all of which are beaten by q, a contradiction to our assumption that q is not the root of T . It is straightforward to see that there is at least one binomial arborescence spanning the set Z and containing the binomial arborescences T1, . . . , Tℓas leaf-subtrees. Such a binomial arborescence (rather the corresponding tournament) can be constructed by starting with the tournaments corresponding to the trees T1, . . . , Tℓand arbitrarily adding matches between surviving players until we construct a knockout tournament on Z. This completes the proof of the lemma.

LCA closure. For an arborescence T and vertex set M in V (T) the least common ancestor-closure (LCA-closure) LCA(M) is obtained by the following process. Initially, set M = M and as long as there are vertices x and y in M whose least common ancestor w is not in M , add w to M . When the process terminates, output M as the LCA-closure of M. See Figure 2 for an illustration of the LCA-closure. We will require the following simple fact regarding the LCAclosure.

Observation 1. Let T be an arborescence and M V (T). Then, |LCA(M)| 2|M|.

We now define a set BT F which depends on AF and T which is an s.b.a rooted at v .

Definition 5. We first set BT F = LCA(AF ). For every pair of vertices u, v AF such that (a) u Desc T (v) \ Child T (v) and (b) there is no other vertex w LCA(AF ) such that w Desc T (v) Ansc T (w), we pick an arbitrary vertex

Figure 2: An illustration of the LCA-closure on a binomial arborescence on 16 vertices. The circled vertices in the first figure depict the set M and those in the second figure depict LCA(M). Observe that in the second figure, the least common ancestor of any pair of circled nodes is also circled.

z Desc T (v) Ansc T (u) and add it to BT F . That is, we pick an arbitrary vertex on the u-v path in T and add it to BT F . Finally, we set BT F := LCA(BT F ).

When T is clear from the context, we simply refer to the set BT F as BF .

Definition 6. Let T be an s.b.a rooted at v and let X V (T) such that v X and LCA(X) = X. Let T be a tree constructed as follows. We begin with T and delete all nodes which do not lie on a v -u path in T for any u X. We then repeatedly short-circuit each node of degree 2 which is not in X. That is, we repeat the following step until we cannot do it anymore. Pick a vertex u V (T) \ X with exactly one in-neighbor u and one out-neighbor u+. Delete the vertex u and add the arc (u , u+). Let T be the tree that remains when the above step can no longer be performed. We call T the topology of X in T.

Since LCA(X) = X, it follows that V (T ) is in fact equal to X. Also, when we talk about a vertex u V (T ), we can also talk about the same vertex u in T since V (T ) V (T). Clearly, the topology of the set X in T must be one of at most |X| ρ(|X|) trees where ρ(p) denotes the number of labeled trees on p vertices. We will make use of the following well known theorem of Cayley.

Proposition 3 (Cayley 1889). ρ(p) = pp 2.

The algorithm. Our algorithm has 4 main phases. We will give a brief description of each phase and give formal proof of correctness at the end. We let π denote the ordering witnessing F and γ the ordering of BF that respects π. For the rest of the description, we fix a hypothetical s.b.a T rooted at v and let HF T denote the topology of BF in T.When F and T are clear from the context, we simply call it H.

Phase I: By definition, V (H) = BF and due to Observation 1 we know that |V (H)| 16k + 8. Hence, in this phase we guess H by iterating over all topologies derived from a set of k O(k) rooted labeled trees on at most 16k + 8 vertices. Note that although we know the set AF , we do not know the

set BF . However, we do not need to know this set at this point and will deal with this fact in the next step. We now state the following observation regarding H which is a direct consequence of the definition of the set BF and is crucial for the correctness of our algorithm. Observation 2. For every u V (H) and v Child H(u) \ Child T (u), either u / AF or v / AF . Consequently, (u, v) A(D) \ F. Phase II: In the second phase, we compute the images of the vertices of V (H) under τ. Note that computing this immediately gives us a (injective) mapping from the vertices in AF to the vertices of H. Formally speaking, we will guess the following function (Definition 7) by going over all functions from V (H) to Types. Definition 7. Let ψF H : V (H) Types be the function that maps vertices of AF in V (H) to themselves and maps the vertices of V (H) \ AF , to their image under τ π γ . That is, ψF H(v) = v if v AF and ψF H(v) = τ π γ (v) otherwise.

Observe that there are only k O(k) functions from V (H) to Types and hence we can guess ψF H by simply iterating over all these functions.

Phase III: In this phase, we guess the number of descendants rooted at each vertex in V (H), in T. This number is the size of the largest subtournament of the tournament given by T which is won by this vertex. We remark that even though at first glance, the number of guesses required here seems too big (n O(k)), it can in fact be bounded by the running time stated in Theorem 1. This is a crucial part of our FPT algorithm. Let sz F H : V (H) [n] denote the function where sz F H(v) = |Desc T (v)| for every v V (H). That is, this function gives the size of the largest subtournament (in T) won by each vertex of V (H). Since we are by definition only interested in balanced knockout tournaments, it follows that the range of sz F H is the set {2i|i [log n] {0}}. Hence, we can represent the function sz using a function χF H : V (H) [log n] {0}. This function is formally defined as follows. Definition 8. For every u V (H), the number of descendants of u in the s.b.a T is 2χF H(u). Hence we have (log n)O(k) choices for the function χF H, which is (k log k)O(k)n O(1) due to Lemma 1. This completes the description of this phase. Before we move to the description of the final phase, we define the notion of X-decompositions of an arborescence T for some set X V (T). We believe that a good understanding of this notion will the give the reader a better intuitive understanding of the final phase. Definition 9. Let T be an arborescence and let X V (T) such that it contains the root and let |X| = ℓ. We say a set T = {T1, . . . , Tℓ} of subtrees of T is the X-decomposition of T if these are precisely the subtrees of T that we obtain by deleting all arcs (u, v) A(T) where v X. We have the following straightforward consequence of the above definition.

Figure 3: An illustration of the X-decomposition of the arborescence T. The vertices of X are green and represented as concentric circles.

Observation 3. Let T be an arborescence and let X V (T) such that it contains the root and let |X| = ℓ. Let T = {T1, . . . , Tℓ} be the X-decomposition of T. Then, the vertex sets V (T1), . . . , V (Tℓ) form a partition of V (T), and for all i [ℓ] there is a vertex ri X such that Ti is an arborescence rooted at ri .

Let T = {T1, . . . , Tℓ} denote the BF -decomposition of T, where ℓ= |BF |. Recall that the trees in T are pairwise vertex disjoint and each tree is rooted at a vertex of BF . Furthermore, since each tree contains exactly one vertex of BF (which is the root of the subtree), it follows that no arc from the set F occurs inside any of these subtrees. We now have the following useful lemma describing the structure of each subtree. Recall that ri is the root of the subtree Ti. Lemma 4. For each i [ℓ], V (Ti) i Types (ri) τ 1(i).

Proof. In order to prove the lemma, it suffices to show that if ri AF , then τ(u) > γ(ri) for every u V (Ti) \ {ri} and if ri / AF , then τ(u) τ(ri) for every u V (Ti). For the first statement, suppose that for some u V (Ti) \ {ri}, τ(u) γ(ri). That is, u beats ri and so π(u) < π(ri). However, since Ti is an arborescence rooted at ri and u V (Ti), it follows that ri has a path to u in Ti and hence it must be the case that there is an arc (x, y) along this path violating the ordering π (that is, π(x) > π(y)), implying that the arc (x, y) is in the set F, a contradiction to the fact that no Ti contains an arc in F. The argument for the second statement is analogous. This completes the proof of the lemma.

Intuitively, the structure guaranteed by the previous lemma implies that we no longer need to concern ourselves with the actual vertices inside each subtree but simply the types of the vertices and the number of vertices of each type. This allows us to phrase the remaining problem as a knapsack-type problem and write an ILP-FEASIBILITY instance with few variables.

Phase IV: In the final phase, we will construct an instance of ILP-FEASIBILITY corresponding to the guesses made so far, solve it using Proposition 2 and return YES if and only

if the answer to this query is YES. We will show that the given instance of TFP is a YES instance if and only if at least one of the constructed ILP-FEASIBILITY instances is a YES instance. Definition 10. We say that a tuple (L, ψ, χ) is valid if L is an arborescence rooted at v , V (L) AF , ψ : V (L) Types such that ψ(u) = u for every u AF , ψ(u) Types \ AF for every u V (L) \ AF and χ : V (L) [log n] {0}. For each valid tuple (L, ψ, χ), we define an instance IL,ψ,χ of ILP-FEASIBILITY over a set of O(k2) variables as follows. For each i Types and u V (L), we have a variable xu i . We now describe the constraints. We have four sets of constraints, which we denote by C1, C2, C3 and C4.

The constraints in C1 are defined as follows. Recall that for each i Types, Pi(τ) is the set of vertices whose image under τ is i. For each i Types, let Pi denote the size of the set Pi(τ). For each i Types, we have a constraint

u V (H) xu i = Pi.

The constraints in C2 are defined as follows. For every u V (L) \ AF , we have the constraint xu ψ(u) 1.

The constraints in C3 are defined as follows. For each u V (L), we have a constraint

i Types (u) xu i = 2χ(u)

x Child H(u) 2χ(x).

The constraints in C4 are defined as follows. For each u V (L) and i Types<(u), we have a constraint xu i = 0.

This completes the description of the instance IL,ψ,χ of ILP-FEASIBILITY. The meaning of the variables and constraints is as follows. Suppose that L = H, ψ = ψF H and χ = χF H. For each u BF , let Qu denote the subtree of T rooted at u and contained in the BF -decomposition of T. The value of xu i will be the number of those vertices in the subtree Qu whose image under τ is i. The constraints essentially require us to pack vertices of each type into the subtrees {Qu|u BF } subject to the type and size restrictions imposed by the functions ψ, χ and λ. The set C1 says that vertices in each τ 1(i) are partitioned across the subtrees {Qu|u BF }. The set C2 says that for every subtree Qu rooted at a vertex u BF , there is at least one vertex of type τ(u) which is contained in Qu, which we know from earlier is the root. To understand the set C3, observe that for every u BF , the set of vertices in Qu are precisely those vertices which are descendants of u in T but not descendants of v for any v Child L(u). Hence, the total number of vertices in Qu is given by the function χ and this is precisely 2χ(u)

x Child H(u) 2χ(x). Furthermore, by Lemma 2, we know that the vertices in Qu only come from those

types in Types (u). Hence the constraints in the set C3 ask to assign vertices from only those types in Types (u) so that the number adds up to the size of Qu.

The set C4 merely complements the set C3 by ensuring that we do not assign any vertex of type Types<(u) = Types \ Types (u) to the tree Qu.

Lemma 5. The given instance of TFP is a YES instance if and only if for some valid tuple (H, ψ, χ), the instance IH,ψ,χ is a YES instance of ILP-FEASIBILITY.

Proof. We first consider the forward direction. Suppose that the given instance is a YES instance and let T be an s.b.a rooted at v . Let H be the topology of BF in T. Let ψ : V (H) Types be the function ψF H (see Definition 7) and let χ be the function χF H (Definition 8). For each u BF , let Qu denote the tree rooted at u in the BF -decomposition of T. We now argue that the instance IH,ψ,χ is a YES instance. For this, we define the assignment xu i = |{q|τ(q) = i, q V (Qu)}| for every i Types and u BF . That is, we assign to variable xu i the number of vertices in Qu whose image under τ is i. The fact that this assignment satisfies all four sets of constraints can be seen by a straightforward examination. Indeed the explanation of the constraints given prior to this lemma shows precisely this. This completes the forward direction of the proof and we now argue the more involved converse direction. Let (H, ψ, χ) be a valid tuple such that IH,ψ,χ is a YES instance. Let α be the assignment of the variables which satisfies the given instance and for each i, u, let αu i denote the value of xu i given by a feasible solution to this instance. We will argue that the given instance of TFP is a YES instance by constructing an s.b.a T rooted at v . For each u V (H) and i Types, we assign a unique subset of Pi(τ) to the pair (u, i). To formally capture this, we define a function ζ : V (H) Types 2V (D) { }. Now, the mapping given by this function has to be defined carefully by performing a bottom up processing of H. Initially, we set ζ(u, i) = for every u V (H) and i Types. We also mark all vertices in V (D) as free. We then exhaustively execute the following procedure and along the way we change the marking of vertices of V (D) from free to taken whenever we assign a set containing them to some u, i under ζ. If there is a vertex u V (H) and an element v Child H(u) such that ζ(v, j) = for every j Types (if u is a leaf of H then it vacuously satisfies this condition), then for every i Types, we set ζ(u, i) to be the weakest αi u vertices in Pi(τ) among those which are free and mark these vertices as taken. If αi u = 0, then we set ζ(u, i) = . The fact that ζ exists follows from the fact that the set of constraints in C1 are satisfied by the values {αu i |u V (H), i Types}. For each u V (H), we define Ru to be the set

i Types ζ(u, i) and we define Yu to be the set

v Desc H(u) Rv. It follows from the definition of ζ that the vertex sets {Ru|u V (H)} form a partition of V (D). Furthermore, since the constraints in C2, C3 and C4 are satisfied by α , it follows that for every u V (H), Ru contains at most one vertex of V (F), Ru contains at least one vertex w of

type ψ(u) (τ(w) = ψ(u)) and Ru

i Types (w) ζ(u, i), implying that the strongest vertex in Ru has type ψ(u). Furthermore, if u is a leaf of H, then Ru = i Types (u) xu i =

i Types xu i = 2χ(u). We will define the s.b.a T by performing a bottom up parse of H. During this parse, for every u V (H), we will define a binomial arborescence Tu which spans Yu and is rooted at ru which is the strongest vertex of type ψ(u) which is contained in Yu. To keep track of the vertices of H which we have processed and those we have not, we will use a boolean function Acc : V (H) {T, F}. Initially, Acc(u) = F for every u V (H). Constructing T. For each u V (H) which is a leaf, we invoke the first statement of Lemma 3 to conclude that there is a binomial arborescence Tu spanning Ru and rooted at ru, which is the strongest element of type ψ(u) in Ru. We then set Acc(u) = T. We now exhaustively repeat the following procedure for the rest of the vertices. Pick a vertex u such that Acc(u) = F and Acc(v) = T for every v Child H(u). Let c1, . . . , cℓdenote the children of u in H and let Tc1, . . . , Tcℓdenote the already defined arborescences where Tcj spans Ycj and is rooted at rcj which is the strongest vertex of type ψ(cj) in Ycj. Define the set Z0 = Ru and for each j [ℓ], the set Zj as V (Tcj). Define the trees T1, . . . , Tℓas Tj = Tcj and the root rj of Tj as rj = rcj. Since the sets {Zj}0 j ℓ, the trees {Tj}j [ℓ] and vertices {rj}j [ℓ] satisfy the premises of the second statement of Lemma 2, we conclude that there is a binomial arborescence Tu rooted at the strongest vertex of Z0 = Ru and spanning the set Yu. Since we have already argued that the strongest vertex of Ru is of type ψ(u), we conclude that Tu is rooted at the strongest vertex of type ψ(u) in Yu. We now set Acc(u) = T and continue. This procedure terminates when u = v and we will have demonstrated the existence of an arborescence rooted at v and spanning V (D). This completes the proof of the lemma.

Theorem 1 follows from Lemma 5, the fact that there are (k log k)O(k)n O(1) valid tuples, and Proposition 2 combined with the fact that the number of variables in each constructed instance of ILP-FEASIBILITY is O(k2).

Concluding remarks. Our fixed-parameter tractability result for the TOURNAMENT FIXING PROBLEM is but the first step in the formal study of the parameterized complexity of this problem. The challenge going forward is to chart the parameterized complexity landscape of the TFP with respect to stronger parameters for tournaments, e.g., feedback vertex set, cutwidth and treewidth. A second direction would be the study of the probabilistic version of the problem where the input is a probability matrix giving the probability of any player beating any other and the objective is to compute a seeding such that the probability of a special player wining the resulting knockout tournament exceeds a given threshold.

Acknowledgments. The authors wish to thank the anonymous reviewers for their helpful comments and acknowledge support by the Austrian Science Fund (FWF, project P26696).

Aziz, H.; Gaspers, S.; Mackenzie, S.; Mattei, N.; Stursberg, P.; and Walsh, T. 2014. Fixing a balanced knockout tournament. In Brodley, C. E., and Stone, P., eds., Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Qu ebec City, Qu ebec, Canada., 552 558. AAAI Press. Betzler, N.; Bredereck, R.; Chen, J.; and Niedermeier, R. 2012. Studies in computational aspects of voting - A parameterized complexity perspective. In Bodlaender, H. L.; Downey, R.; Fomin, F. V.; and Marx, D., eds., The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science, 318 363. Springer Verlag. Bevern, R. v.; Komusiewicz, C.; Molter, H.; Niedermeier, R.; Sorge, M.; and Walsh, T. 2016. h-index manipulation by undoing merges. In Kaminka, G. A.; Fox, M.; Bouquet, P.; H ullermeier, E.; Dignum, V.; Dignum, F.; and van Harmelen, F., eds., ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016), volume 285 of Frontiers in Artificial Intelligence and Applications, 895 903. IOS Press. Cayley, A. 1889. A theorem on trees. Quart. J. Math. 23:376 378. Chen, J.; Faliszewski, P.; Niedermeier, R.; and Talmon, N. 2015. Elections with few voters: Candidate control can be easy. In Bonet, B., and Koenig, S., eds., Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., 2045 2051. AAAI Press. Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; and Saurabh, S. 2015. Parameterized Algorithms. Springer. Dey, P.; Misra, N.; and Narahari, Y. 2015. Kernelization complexity of possible winner and coalitional manipulation problems in voting. In Weiss, G.; Yolum, P.; Bordini, R. H.; and Elkind, E., eds., Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4-8, 2015, 87 96. ACM. Downey, R. G., and Fellows, M. R. 2013. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer. Flum, J., and Grohe, M. 2006. Parameterized Complexity Theory, volume XIV of Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer Verlag. Fradkin, A. O., and Seymour, P. D. 2013. Tournament pathwidth and topological containment. J. Comb. Theory, Ser. B 103(3):374 384. Frank, A., and Tardos, E. 1987. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1):49 65. Hemaspaandra, L. A.; Lavaee, R.; and Menton, C. 2016. Schulze and ranked-pairs voting are fixed-parameter tractable

to bribe, manipulate, and control. Ann. Math. Artif. Intell. 77(3-4):191 223. Kannan, R. 1987. Minkowski s convex body theorem and integer programming. Math. Oper. Res. 12(3):415 440. Kim, M. P., and Vassilevska Williams, V. 2015. Fixing tournaments for kings, chokers, and more. In Yang, Q., and Wooldridge, M., eds., Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, 561 567. AAAI Press. Kim, M. P.; Suksompong, W.; and Vassilevska Williams, V. 2016. Who can win a single-elimination tournament? In Schuurmans, D., and Wellman, M. P., eds., Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA., 516 522. AAAI Press. Lenstra, H. W., and Jr. 1983. Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538 548. Lindner, C., and Rothe, J. 2008. Fixed-parameter tractability and parameterized complexity, applied to problems from computational social choice. In Mathematical Programming Glossary. Informs Computing Society, 1 15. Stanton, I., and Vassilevska Williams, V. 2011. Rigging tournament brackets for weaker players. In Walsh, T., ed., IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, 357 364. IJCAI/AAAI. Vassilevska Williams, V. 2010. Fixing a tournament. In Fox, M., and Poole, D., eds., Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press. Vu, T.; Altman, A.; and Shoham, Y. 2009. On the complexity of schedule control problems for knockout tournaments. In Sierra, C.; Castelfranchi, C.; Decker, K. S.; and Sichman, J. S., eds., 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, May 10-15, 2009, Volume 1, 225 232. IFAAMAS. Yang, Y. 2014. Election attacks with few candidates. In Schaub, T.; Friedrich, G.; and O Sullivan, B., eds., ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014), volume 263 of Frontiers in Artificial Intelligence and Applications, 1131 1132. IOS Press.