On Succinct Encodings for the Tournament Fixing Problem

1 Introduction

Single-elimination (or knockout) tournaments are natural models of competitive environments such as sports competitions, decision making and elections. Consequently, they have attracted a great deal of attention in Artificial Intelligence, especially within social choice theory [Laffond et al., 1993; Fisher and Ryan, 1995; Brandt et al., 2016; Williams, 2016; Brandt et al., 2018].

Formally, the execution of a knockout tournament with a set N of n players is described by a complete (unordered) binary tree T with n leaves and a mapping ϕ : N → leaves(T ), called a seeding. In the first round, pairs of players mapped to leaves with the same parent compete against each other, and the winner is mapped to the common parent. The leaves are then deleted from the tree, and the next round is conducted similarly. The execution stops when the tree contains a single vertex, mapped to a player who is then declared the winner.

More recent years have seen an increased interest in the structure of knockout tournaments which might be amenable to manipulation by an external agent who may, either bribe certain participants to throw games ([Russell and Walsh,

2009; Kim and Vassilevska Williams, 2015; Mattei et al., 2015; Gupta et al., 2018b]) or rearrange the initial seeding (rigging) [Vu et al., 2009; Vassilevska Williams, 2010; Stanton and Vassilevska Williams, 2011; Aziz et al., 2014; Kim and Vassilevska Williams, 2015; Kim et al., 2016] in order to ensure that a certain player wins the tournament. In this paper, we focus on the latter.

The most natural computational problem associated with rigging tournaments is the TOURNAMENT FIXING PROBLEM (TFP) where, we are given a tournament (an oriented complete graph) D = (N, A). For every u, v ∈ N, we assume (or predict) that in a match between u and v, u would beat v if and only if (u, v) ∈ A. For a given player v⋆ ∈ N, the objective is to decide whether there is a seeding of the n players such that v⋆ is the winner of the resulting knockout tournament, given the match outcomes encoded by D. [Aziz et al., 2014] showed that TFP is NP-hard in general. Moreover, motivated by the fact that TFP is easily solved on acyclic tournaments, they initiated the study of the complexity of TFP parameterized by the feedback arc set number of the tournament, which is the least number of arcs in the given tournament that need to be flipped to obtain an acyclic (or transitive) tournament.

[Aziz et al., 2014] gave a clever nf(k) -time dynamic programming algorithm (for some function f) for this problem, where k is the feedback arc set number of the tournament. Their algorithm clearly runs in polynomial time for every fixed value of k. Subsequently, [Ramanujan and Szeider, 2017] gave a 2O(k2 log k)nO(1) -time algorithm for this problem, which implies polynomial-time solvability as long as k2 log k = O(log n). This bound was recently improved by [Gupta et al., 2018a], who gave a 2O(k log k)nO(1) -time algorithm for this problem.

However, in spite of these recent developments on solving TFP, the feasibility of efficient preprocessing for this problem remained an intriguing open question. The framework of kernelization [Downey and Fellows, 2013; Cygan et al., 2015] offers a mathematically rigorous way of designing, analysing and comparing preprocessing algorithms for numerous problems and has been a resounding success over the last two decades. The notion of efficient preprocessing is captured in this framework by the idea of a polynomial kernelization, which is a polynomial-time algorithm that returns an instance equivalent to the input such that the size of the output is bounded by a polynomial function of some parameter of the input instance.

Our Contribution. In this paper, we present the first polynomial kernelization for TFP parameterized by the feedback arc set number of the input tournament. At the heart of our result is a complex polynomial-time routine that outputs an equivalent SAT encoding of a given input instance of TFP, such that the number of clauses and variables are bounded polynomially in the feedback arc set number and therefore independent of the size of the original tournament. Pipelining our SAT encoding with a chain of known polynomial-timemapping reductions from SAT to TFP, we obtain our polynomial kernel for TFP.

2 Preliminaries

For a digraph D, a feedback arc set is a set of arcs whose reversal in D results in a directed acyclic graph (DAG). An arborescence is a rooted directed tree such that all arcs are directed away from the root.

Definition 1 ([Vassilevska Williams, 2010]). The set of binomial arborescences over a tournament D is recursively defined as follows. (i) Each a ∈ V (D) is a binomial arborescence rooted at a. (ii) If, for some i > 0, Ta and Tb are 2i-1 -node binomial arborescences rooted at a and b, respectively, then the tree T resulting from adding an arc from a to b is the 2i -node binomial arborescence (b.a) rooted at a. If a binomial arborescence T is such that V (T) = V (D), then T is a spanning binomial arborescence (s.b.a.) of D.

We will often refer to a binomial arborescence simply as a b.a and spanning binomial arborescence as an s.b.a.

Proposition 1 ([Vassilevska Williams, 2010]). Let D be a tournament and let v⋆ ∈ V (D). Then, there is a seeding of V (D) such that the resulting knockout tournament is won by v⋆ if and only if D has an s.b.a rooted at v⋆ .

Note that if T is an s.b.a of D, then ∀v ∈ V (T), ∃i ∈ [log n] ∪ {0} such that v has 2i descendants in T and v is the winner of a subtournament played by the descendants of v in T . We use the terms vertex and player interchangeably.

Definition 2. Let Dbe a tournament with a special player v⋆ . Let F ⊆ A(D) be a feedback arc set of D, and let D†

the DAG obtained by reversing the arcs of F in D. Let π : V (D) → [n] be the linear ordering of the players in decreasing order of strength: a player u appears before player v if and only if (u, v) ∈ A(D† ). Then, we say that π witnesses F . We call the vertices in {v⋆ } ∪ V (F) affected vertices and denote this set by AF .

We say that a permutation γ of X ⊆ V (D) respects the permutation π witnessing F if the vertices of X appear in the same order (relative to each other) in γ as they do in π.

We now consider the 'type' function that partitions the vertices in V (D) \AF into at most |AF | +1 partitions. We first define the set Types = [|AF | + 1] ∪ {AF }.

Definition 3. Let Dbe a tournament with a special player v⋆ . Let F ⊆ A(D) be a feedback arc set of D, let π be the ordering witnessing F, and let γ be the ordering of AF that respects π. Define the type function τ π γ : V (D)→Types as follows. For any v∈AF , τ π γ (v)=v. For any v∈V (D)\AF , τ π γ (v) = i where i is the smallest index in [|AF |] such that π(v) < π(γ(i)). If no such index exists, that is, π(v) > π(γ(|AF |)), then τ π γ (v)=|AF |+1. For any i∈Types, denote the set of vertices in the pre-image of i under τ π γ by Pi(τ π γ ).

Observe that vertices of the same type have the same behaviour with respect to every vertex of a different type in the graph. Henceforth, we assume without loss of generality that instances of TFP are of the form (D, k, v⋆ , F, π), where F is a given feedback arc set of D of size O(k) and π is the ordering witnessing F .

In a parameterized problem, inputs are tuples (I, k) where I ∈ Σ∗ is the problem instance and k ∈ N is called the parameter. Let Π ⊆ Σ∗ × N be a parameterized problem and g be a computable function. We say that Π admits a kernel of size g if there exists an algorithm referred to as a kernelization (or a kernel) that, given (x, k) ∈ Σ∗ ×N, outputs in time polynomial in |x| + k, a pair (x′ , k′ ) ∈ Σ∗ ×N such that (a) (x, k) ∈ Π if and only if (x′ , k′ ) ∈ Π, and (b) max{|x′ |, k′ } ≤ g(k). If g(k) = kO(1) , then we say that Π admits a polynomial kernel.

A polynomial compression of a parameterized language Q ⊆ Σ∗ ×N into an unparameterized language R ⊆ Σ∗ is an algorithm that takes as input an instance (x, k) ∈ Σ∗ × N, works in time polynomial in |x| + k, and returns a string y ∈ Σ∗ such that: (a) |y| ≤ p(k) for some polynomial p(·), and (b) y ∈ R if and only if (x, k) ∈ Q.

3 Polynomial Compressions

Due to the 2O(k log k)nO(1) algorithm of Gupta et al. [2018a], we may assume henceforth that k log k ≥ logn. Indeed, if this were not the case, then their algorithm would already be a polynomial-time algorithm for TFP.

Let ̂DF denote the subtournament induced on AF . Moreover, for each i ∈ Types, we denote by µ(i) the number of vertices of type i. Given D, k, v⋆ , F, π, we denote by ω(D, k, v⋆ , F, π) the combined bit-string encoding of ̂DF , k, v⋆ , γ (the relative ordering of AF in π), and µ(i) for every i ∈ Types. Since ̂DF has O(k) vertices and the bit-size of µ(i) is bounded by logn ≤ k log k for every i ∈ Types, it follows that ω(D, F, π) = O(k2 log k). Moreover, observe that given D, k, v⋆ , F, π and F, the string ω(D, k, v⋆ , F, π) can be computed in polynomial time.

Define the language Q ⊆ {0, 1}∗ to be the set {ω(D, k, v⋆ , F, π) | (D, k, v⋆ , F) is a yes-instance of TFP}. Since given ω(D, k, v⋆ , F, π), the tournament D is uniquely defined, we have obtained a polynomial compression of TFP into the language Q. However, note that the most natural certificate of membership in Q is a seeding of the players resulting in a knockout tournament won by v⋆ (equivalently, an s.b.a contained in D and rooted at v⋆ ) and has size (|V (D)|) that, in general, could be superpolynomial in the length of the input (O(k2 log k)). Hence, it is not clear that we have a polynomial test for membership of Q. We now proceed to build on techniques from [Ramanujan and Szeider, 2017] and [Gupta et al., 2018a] to obtain a different compression for this problem, which forms the crux of our SAT encoding.

3.1 Packing-Based Variant

In this subsection, we interpret the work of Gupta et al. [2018a] in terms of a packing variant.

For an arborescence T and vertex set M ⊆ 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, y ∈ 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.

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

We define a refinement of the notion of a template tree of [Ramanujan and Szeider, 2017] and [Gupta et al., 2018a] as follows. Let T be a b.a rooted at v⋆ and let X ⊆ V (T) such that v⋆ ∈ X. Let Z = LCA(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 ∈ Z. For every x, y ∈ Z such that x is an ancestor of y in T ′ and there is no other vertex of Z which is an internal node of the x-y path in T ′ , we add to Z the unique child of x which lies on this x-y path in T ′ . (In [Ramanujan and Szeider, 2017], an arbitrary internal node (if one exists) was added to Z, and in [Gupta et al., 2018a], no internal node was added.) We then repeatedly short-circuit each node of degree 2 in T ′ which is not in Z. That is, we repeat the following step as long as possible: pick a vertex u ∈ V (T ) \ Z with exactly one in-neighbor u- and one out-neighbor u+; delete 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 template tree of X in T .

Observe that the vertex set of the template tree T ′′ of X in the above definition is the set Z, whose size at most 2|LCA(X)| ≤ 4|X| (by Observation 1), and it contains the set X. Moreover, the leaves of T ′′ are contained in X.

Definition 4. A tuple (L, ψ, χ, ℓ) is valid for an instance (D, k, v⋆ , F) if the following conditions hold.

1. L is an arborescence on at most 4(2k + 1) nodes rooted at v⋆ such that V (L) ⊇ AF and leaves(L) ⊆ AF ,
2. ψ : V (L) → Types such that ψ(u) = u for every u ∈ AF , and ψ(u) ∈ Types \ AF for every u ∈ V (L) \ AF ,
3. χ : V (L) → [log n] ∪ {0} where χ(v⋆ ) = log n,
4. ℓ : A(L) → [logn] ∪ {0}, and
5. for each (u, v) ∈ A(L) with ℓ(u, v) = 0, either ψ(u) = ψ(v) or vertices of type ψ(u) beat vertices of type ψ(v).

We relate the definition above with binomial arborescence via the notion of a template tree as follows.

Definition 5. A tuple (L, ψ, χ, ℓ) is realizable for an instance (D, k, v⋆ , F) if it is valid and there is an n-node b.a T rooted at v⋆ with V (L) ⊆ V (T ) such that the following hold: (i) L is the template tree of AF in T , (ii) for each u ∈ V (L), the number of nodes in the subarborescence of T rooted at u is 2χ(u) , and (iii) for each (u, v) ∈ A(L), the number of internal nodes on the path from u to v in T is ℓ(u, v).

In the above definition, T is said to witness the realizability of this valid tuple. With each valid tuple (L, ψ, χ, ℓ), we associate a "packing condition". Specifically, we say that (L, ψ, χ, ℓ) is packable if there exists a partition P of V (D) and a mapping f : V (L) ∪ A(L) → P that satisfies the following constraints.

1. For each u ∈ V (L), we have (i) |f(u)| = 2χ(u) - ∑v∈ChildL(u) (2χ(v) + ℓ(u, v)), (ii) for each v ∈ f(u), v is beaten by some vertex of type ψ(u), and (iii) there exists a vertex of type ψ(u) in f(u).
2. For each (u, v) ∈ A(L), we have (i) |f(u, v)| = ℓ(u, v), and (ii) for each w ∈ f(u, v), w is beaten by some vertex of type ψ(u) but beats some vertex of type ψ(v).

The following proposition follows (though not stated explicitly) from the work of Gupta et al. [2018a],

Proposition 2. A given instance of TFP is a yes-instance if and only if some realizable tuple (L, ψ, χ, ℓ) is packable.

We define the language W ⊆ {0, 1}∗ to be the set {ω(D, k, v⋆ , F, π) | (D, k, v⋆ , F, π) has a realizable tuple (L, ψ, χ, ℓ) that is packable}. Proposition 2 then implies a polynomial compression of TFP into the language W. However, W is also not easily seen to be in NP as the natural certificate consists of a tuple (L, ψ, χ, ℓ) and a partition P; while it is not difficult to substitute every set in P with a function that only states how many vertices of each type belong to that set and use that as a witness (we will do this later), it is not clear how to verify that (L, ψ, χ, ℓ) is realizable-in particular, the dynamic programming algorithm of Gupta et al. [2018a] for this task takes time polynomial in |V (D)| that, in general, could be superpolynomial in the input length (O(k2 log k)).

We next give an explicit reduction from Q to CNF-SAT. (In turn, this reduction implies that Q and W are in NP.)

4 The CNF-SAT Encoding

Due to lack of space, we describe each subformula that will be part of our final output CNF-SAT formula only in words. However, we present our descriptions in such a way that it is straightforward to write it as an AND of clauses. Moreover, we use intuitive terminology for the subformulas as often as possible in order to facilitate readability.

The main idea in our reduction is to simulate the "guessand-verify" operation for instances of W as a test for the satisfiability of an appropriate CNF formula. Towards that, let Dummy = {d1, . . . , dℓ} be a set of ℓ = 4(2k + 1) - |AF | "dummy" nodes. Intuitively, the dummies are placeholders for the (unknown) vertices outside AF that either (i) belong to in LCA(AF ) in the (unknown) template tree L, or (ii) are the children of these vertices. We distinguish between the two types of dummies via the following lemma, which is a direct consequence of the definition of template trees.

Lemma 1. Let (L, ψ, χ, ℓ) be a realizable tuple for an instance (D, k, v⋆ , F). For each u ∈ V (L) \ AF , we have u ∈ LCA(AF ) in any s.b.a that witnesses the realizability of this tuple if and only if u has at least two children in L.

We require the following set of variables.

• ∀ two distinct elements u, v ∈ AF ∪ Dummy where v ̸= v⋆ , we have a variable xLu→v to indicate that u is the parent of v in the (unknown) template tree L. (Only dummies assigned a parent will be considered as part of the tree.) We exclude v⋆ to assert that it is the root of L.
• ∀ dummy u ∈ Dummy and type i ∈ Types \ AF , we have a variable xψu⇐i to indicate that ψ assigns the type i to u.
• ∀u ∈ AF ∪ Dummy and "bit-index" b ∈ [log n] ∪ {0}, we have a variable xχ,b u to indicate whether the bth bit (where the least significant one is indexed by 0) of 2χ(u) is 1.
• ∀ distinct u, v ∈ AF ∪ Dummy where v ̸= v⋆ and "bitindex" b ∈ [log log n] ∪ {0}, we have a variable xℓ,b u→v to indicate whether the bth bit of ℓ(u, v) is 1.
• ∀ element u ∈ (AF ∪ Dummy) \ {v⋆ } and "distance" d ∈ [logn], we have a variable xdist,d u to indicate that there is a path of length d from v⋆ to u in L. (These variables are necessary for a compact encoding of a formula that will be given to ensure the validity of (L, ψ, χ, ℓ).)
• ∀e ∈ AF ∪Dummy∪((AF ∪Dummy)×(AF ∪Dummy)) (i.e., e is a single element or a pair of elements from AF ∪ Dummy), type i ∈ Types \ AF and "bit-index" b ∈ [logn] ∪ {0}, we have a variable xg,b
• e,i to indicate whether the bth bit of g(e, t) is 1. Here, g is the witness of the satisfaction of the implicit packing condition which will be defined in Section 4.2.
• Additional "local variables" (where a local variable is one used in a single specific formula for implementation purposes) will be presented when required.

4.1 Constraints for the Realizability of (L, ψ, χ, ℓ)

We first present constraints that assert that (L, ψ, χ, ℓ) is valid. To assert that L is an arborescence, the following lemma will come in handy.

Lemma 2. Let L be a digraph where v⋆ ∈ V (L) has indegree 0. Then, L is an arborescence rooted at v⋆ of height at most log n if and only if the following conditions hold.

• Each vertex u ∈ V (L) \ {v⋆ } has in-degree at most 1.
• For each u ∈ V (L) \ {v⋆ }, there is i ∈ [log n] such that L has a path of length i from v⋆ to u.

Lemma 2 is based on the fact that L is an arborescence rooted at v⋆ if and only if every vertex other than v⋆ has indegree exactly 1 and is reachable from v⋆ . The same fact helps us identify those dummies which participate in L and to ensure that V (L) ⊇ AF . Towards this, the following definition and lemma will be useful.

Definition 6. Let L′ be a digraph where v⋆ ∈ V (L) has indegree 0. Then, the reachability digraph of v⋆ in L′ is the subgraph of L′ induced by the set of v⋆ and the other vertices u ∈ V (L′ ) such that L′ has a path of length i from v⋆ to u for some i ∈ [log n].

Lemma 3. Let L be an arborescence rooted at v⋆ of height at most log n. Then, there exists a digraph L′ where every vertex u ∈ V (L′ ) \ {v⋆ } has in-degree at most 1, the reachability digraph of v⋆ in L′ is precisely L, and every leaf in L has out-degree 0 in L′ .

We now present the constraints.

1. For every u ∈ (AF ∪ Dummy) \ {v⋆ }, the formula AtMostOneParent(u) is true if and only if at most one variable in {xLv→u : v ∈ (AF ∪ Dummy) \ {u}} is true.
2. For every u ∈ Dummy, the formula ExactlyOneType(u) is true if and only if exactly one variable in {xψu⇐i : i ∈ Types \AF} is true.
3. For every u ∈ AF ∪ Dummy, the formula ExactlyOneSizeBit(u) is true if and only if exactly one variable in {xχ,b u : b ∈ [logn] ∪ {0}} is true. Moreover, xχ,log n v⋆ is true.
4. For every u ∈ (AF ∪ Dummy) \ {v⋆ }, the formula AtMostOneDist(u) is true if and only if at most one variable in {xdist,d u : d ∈ [logn]} is true.
5. For every u ∈ AF \{v⋆ }, the formula AtLeastOneDist(u) is true if and only if there exists d ∈ [log n] such that xdist,d u is true. We note that this set of constraints will ensure that V (L) ⊇ AF .
6. For every u ∈ AF \ {v⋆ } and d ∈ [logn], the formula VerifyDistd(u) is true if and only if xdist,d u is true and either (i) d = 1 and xLv⋆→u is true, or (ii) d ≥ 2 and there is a w ∈ (AF ∪ Dummy) \ {v⋆ , u} such that both xLw→u and xdist,d-1 w are true.
7. For each u ∈ Dummy, the formula Reachable(u) is true if and only if there is a d ∈ [log n] such that xdist,d u is true.
8. For every u ∈ Dummy, the formula NotLeaf(u) is true if and only if Reachable(u) is false or there exists w ∈ (AF ∪Dummy)\{v⋆ , u} such that xLu→w is true. This set of constraints will be used to ensure that leaves(L) ⊆ AF .

We now introduce a few formulas that will be used several times. First, we identify the nodes and arcs of L as follows. For every u ∈ AF ∪ Dummy, the formula IsNode(u) is true if and only if either u ∈ AF or both u ∈ Dummy and Reachable(u) is true. Moreover, for every two distinct elements u, v ∈ AF ∪Dummy, the formula IsArc(u, v) is true if and only if v ̸= v⋆ , IsNode(u) is true, IsNode(v) is true, and xLu→v is true. Additionally, for every two distinct elements u, v ∈ AF ∪ Dummy, the formula Beats(u, v) is true if and only if there exist i, j ∈ Types such that the following conditions hold: (i) i = j or vertices of type i beat vertices of type j; (ii) either u = i ∈ AF or both u /∈ AF and xψu⇐i is true; (iii) either v = j ∈ AF or both v /∈ AF and xψv⇐j is true.

To validate Condition 5 in Definition 4, we ensure that for every two distinct elements u, v ∈ AF ∪Dummy, the formula IfArcThenValid(u, v) is true if and only if, if IsArc(u, v) is true, then Beats(u, v) is true.

LCA-Closure. Based on Lemma 1, we determine whether a dummy belongs to the LCA-closure as follows. For every u ∈ Dummy, we have a formula InClosure(u) that is true if and only if IsNode(u) is true and there exist two distinct q, p ∈ (AF ∪ Dummy) \ {v⋆ , u} such that both xLu→p and xLu→q are true. Moreover, for every u ∈ Dummy, we have a formula ChildOfClosure(u) that is true if and only if IsNode(u) is true and InClosure(u) is false. To verify that every degree-2 dummy is indeed a child of a node in the LCAclosure, for every two distinct u, v ∈ Dummy, we have a formula NoDeg2ConsecDum(u, v) that is true if and only if, if both IsArc(u, v) is true and ChildOfClosure(u) is true, then ChildOfClosure(v) is false.

A crucial ingredient of our encoding is a "local check" to verify whether the size logarithms assigned by χ enable the existence of a b.a that gives rise to L as per Definition 5. (Not all sizes enable this-for example, if n = 16, L is a star with 6 nodes, and each leaf is assigned size 2, the tuple is not realizable; indeed, v⋆ has only 4 incomparable children whose subtrees have size 2, see Fig. 1). This ingredient is encapsulated in Lemma 5. (The first item has already been validated.) Towards its presentation and proof, the following lemma will be useful.

Lemma 4. 1. Let T be a b.a, and let u ∈ V (T). Then, the subarborescence rooted at u is a b.a.

1. For any set of nodes U, r ∈ U and χ : U → [logn] ∪ {0}, there exists a b.a rooted at r where each node in U \ {r} is a child of r and for each u ∈ U the size of the subarborescence rooted at u is 2χ(u) if and only if χ is injective and χ(r) > χ(u) for each u ∈ U.
2. For any two nodes r and u, χ : {r, u} → [logn] ∪ {0} and ℓ ∈ [logn] ∪ {0}, there exists a b.a rooted at r with a path of ℓ internal nodes from r to u and where for each v ∈ {r, u} the size of the subarborescence rooted at v is 2χ(v) if and only if 2χ(r) ≥ 2χ(u)+ℓ+1 .

Proof. (1) and (2) followdirectly fromDefinition 1, while (3) can be proved by fixing r, u and χ : {r, u} → [log n] ∪ {0} and performing a straightforward induction on ℓ.

Based on Lemmas 1 and 4, we have the following useful characterization of realizable tuples.

Lemma 5. Let (L, ψ, χ, ℓ) be a valid tuple for an instance (D, k, v⋆ , F). Then, (L, ψ, χ, ℓ) is realizable if and only if the following conditions are satisfied.

1. There does not exist an arc (u, v) ∈ A(L) such that u, v /∈ AF and both u and v have degree 2 in L.
2. For every arc (u, v) ∈ A(L) such that u ∈ AF or u has degree at least 3 in L, we have ℓ(u, v) = 0.
3. For every arc (u, v) ∈ A(L), χ(u) > χ(v).
4. For every u ∈ V (L) of degree at least 3 and any two distinct children v, w of u in L, we have χ(v) ̸= χ(w).
5. For every arc (u, v) ∈ A(L) such that u /∈ AF and v is the only child of u in L, we have 2χ(u) ≥ 2χ(v)+ℓ(u,v)+1 .

Proof. ( =⇒ ) (1) follows from Lemma 1, (2) follows from the definition of template trees and realizability, (3) follows from Lemma 4 (2), (4) follows from the second statement of this lemma and Definition 1, and (5) follows from by Lemma 4 (3).

( ⇐= ) For every leaf u of L, we root a 2χ(u) -node b.a at u. For every (u, v) ∈ A(L), we subdivide it exactly ℓ(u, v) times to obtain an arborescence L′ of height log n rooted at v⋆ which, (using the 5 properties in the premise) can be seen to be a subgraph of an s.b.a. Therefore, we use χ(u) for every u ∈ V (L) to root (or reconstruct) appropriately sized b.a's at every node of V (L) and for each (u, v) ∈ A(L), use ℓ(u, v) and the height of v in L′ to reconstruct the b.a's rooted at the newly created subdivision vertices. It is easy to prove that assuming the given 5 properties, this is always possible and moreover, the resulting s.b.a T rooted at v⋆ indeed witnesses the realizability of the given tuple.

For Condition 2 in Lemma 5, for each distinct u, v ∈ AF ∪ Dummy, the formula LocCheckLenSensible(u, v) is true if and only if, if both (i) IsArc(u, v) is true, and (ii) either u ∈ AF or u ∈ Dummy and InClosure(u) is true, then for every b ∈ [log log n] ∪ {0}, xℓ,b u→v is false.

To validate Condition 3 in Lemma 5, for every two distinct elements u, v ∈ AF ∪ Dummy, the formula LocCheckSizeDec(u, v) is true if and only if, if IsArc(u, v) is true, then the largest b ∈ [logn] ∪ {0} such that xχ,b u and xχ,b v are either not both true or not both false exists and is such that xχ,b u is true and xχ,b v is false.

To validate Condition 4 in Lemma 5, for every three distinct elements u, v,w ∈ AF ∪ Dummy, the formula LocCheckSizeDiff(u, v,w) if true if and only if, if both IsArc(u, v) and IsArc(u,w) are true, then there exists b ∈ [logn] ∪ {0} such that either both xχ,b v is true and xχ,b w is false or both xχ,b v is false and xχ,b w is true.

To validate Condition 5 in Lemma 5, we need to implement standard binary addition. For this, we introduce local variables. Specifically, for every two distinct elements u, v ∈ AF ∪ Dummy and b ∈ [log n] ∪ {0}, we have a new variable yLocCheckPath (u,v),b to indicate whether the bth bit in the binary encoding of the (nonnegative) integer

where we use [z] (for any variable z) to denote 1 if z is true and 0 otherwise. Towards this, for every two distinct elements u, v ∈ AF ∪ Dummy and b ∈ [log] ∪ {0}, we have a new variable zLocCheckPath (u,v),b to indicate whether the bth bit in the binary encoding of the (nonnegative) integer 2∑log log n i=0 [xℓ,i u→v ]·2i . Then, for every two distinct elements u, v ∈ AF ∪ Dummy, for every function f : {[log logn] ∪ {0}} → {0, 1} (because there are only O(log n) such functions, the number of formulas to consider is kO(1) ), we have a formula that is satisfied if and only if, if for every i ∈ [log logn] ∪ {0} we have that f(i) = 1 if and only if xℓ,i u→v is true, then for every b ∈ [logn] ∪ {0} we have that zLocCheckPath (u,v),b is true if and only if b = ∑log log n i=0 f(i) · 2i -1. To validate the "y-variables", for every two distinct elements u, v ∈ AF ∪ Dummy and b ∈ [logn - 1] ∪ {0}, we also have a new variable cLocCheckPath (u,v),b and a formula that is satisfied if and only either (i) b = 0 and both xχ,0 v and zLocCheckPath (u,v),0 are true, or (ii) b ≥ 1 and at least two among xχ,b v , zLocCheckPath (u,v),b and cLocCheckPath (u,v),b-1 are true. Note that the "c-variables" are meant to encode carry-overs in addition computations. Now, for every two distinct elements u, v ∈ AF ∪ Dummy and b ∈ [logn] ∪ {0}, we have a formula that is satisfied if and only if either (i) b = 0 and yLocCheckPath (u,v),0 is true if and only if exactly one variable among xχ,0 v and zLocCheckPath (u,v),0 is true, or (ii) b ≥ 1 and yLocCheckPath (u,v),b is true if and only if exactly one variable or exactly three variables among the variables xχ,b v , zLocCheckPath (u,v),b and cLocCheckPath (u,v),b-1 are true.

Lastly, for every two distinct elements u, v ∈ AF ∪ Dummy, the formula LocCheckPath(u, v) is true if and only if, if both IsArc(u, v) and ChildOfClosure(v) are true, then either (i) for every b ∈ [logn] ∪ {0}, the two variables xχ,b u and yLocCheckPath (u,v),b are both true or both false, or (ii) the largest b ∈ [logn] ∪ {0} such that xχ,b u and yLocCheckPath (u,v),b are either not both true or not both false is such that xχ,b u is true and yLocCheckPath (u,v),b is false.

The REALIZABLE formula. We define the formula REALIZABLE as the AND of the following formulas: (i) every formula in items 1-8 in "Validity"; (ii) for every two distinct elements u, v ∈ AF ∪ Dummy, the formulas IfArcThenValid(u, v), LocCheckLenSensible(u, v), LocCheckSizeDec(u, v) and LocCheckPath(u, v); (iii) for every three distinct elements u, v,w ∈ AF ∪ Dummy, the formula LocCheckSizeDiff(u, v, w).

4.2 Constraints for the Packing-Based Condition

We rephrase the packing condition as follows. We say that (L, ψ, χ, ℓ) is implicitly packable if there exists a function g : (V (L) ∪ A(L)) × Types → [n] ∪ {0} that satisfies:

1. For each u ∈ V (L), we have (i) | ∑t∈Types g(u, t)| = 2χ(u) - ∑v∈ChildL(u) (2χ(v) + ℓ(u, v)), (ii) for each t ∈ Types such that g(u, t) ≥ 1, either ψ(u) = t or vertices of type t are beaten by vertices of type ψ(u), and (iii) g(u, ψ(u)) ≥ 1.
2. For each (u, v) ∈ A(L), we have (i) | ∑t∈Types g((u, v), t)| = ℓ(u, v), and (ii) for each t ∈ Types such that g(u, t) ≥ 1, there exists a vertex of type t that is beaten by some vertex of type ψ(u) but beats some vertex of type ψ(v).
3. For each t ∈ Types, | ∑e∈V (L)∪A(L) g(e, t)| = µ(t).

It can be verified that the following statement holds true. (For lack of space, we omit a proof.)

Lemma 6. Let (L, ψ, χ, ℓ) be a realizable tuple for an instance (D, k, v⋆ , F). Then, (L, ψ, χ, ℓ) is packable if and only if it is implicitly packable.

Thus, Proposition 2 implies the following lemma.

Lemma 7. A given instance of TFP is a yes-instance if and only if some realizable tuple (L,ψ,χ,ℓ) is implicitly packable.

By arguments similar to those in the previous subsection, it is not difficult to validate (in CNF-SAT) the satisfaction of each of the three constraints in the definition of the implicit packing condition. For lack of space, we omit these details. The formula to be generated in this subsection is denoted by PACKABLE; we state its properties in the next subsection.

The output of the reduction is ϕ = ϕ(D, k, v⋆ , F) = REALIZABLE ∧PACKABLE. Then, the following holds.

Observation 2. The size of the formula ϕ is polynomial in k, and it is computable in polynomial time.

We have defined ϕ in such a way that a satisfying assignment for ϕ corresponds precisely to the tuple (L, ψ, χ, ℓ, g) where (L, ψ, χ, ℓ) is a realizable tuple and is implicitly packable (using the function g). Conversely, given a realizable tuple (L, ψ, χ, ℓ) and the function g certifying that this tuple is implicitly packable, one can construct a satisfying assignment for ϕ. This proves our main theorem.

Theorem 1. TFP admits a polynomial compression into CNF-SAT.

5 Outline of the Kernelization Algorithm

[Aziz et al., 2014] give a polynomial-time reduction to TFP from the variant of 3-SAT where every literal appears at most twice. Call this reduction D. This variant of 3-SAT can be easily seen to be NP-hard by a simple reduction from 3-SAT where one creates distinct copies of each variable for each of its literals and then finally adds a 2-CNF formula encoding the equality among these copies. Call this reduction from 3SAT, E. Finally, let F denote the standard polynomial-time reduction from CNF-SAT to 3-SAT.

Let Q denote the composed algorithm D ◦ E ◦ F which takes as input a CNF-SAT instance, runs Algorithm F on it, then Algorithm E on the output of F and finally, Algorithm D on the output of E. Notice that Q is a polynomial-time reduction from CNF-SAT to TFP. Executing Q on our CNFSAT encoding results in the polynomial kernelization for TFP parameterized by the feedback arc set number.

6 Conclusions and Future Research

Our CNF-SAT encoding for the Tournament Fixing Problem with output size bounded polynomially in the feedback arc set number of the input is pleasantly surprising because TFP is a graph layout problem and designing even fixed-parameter tractable algorithms for such problems is quite challenging, let alone kernelization algorithms. Moreover, combining our SAT encoding with state-of-the-art SAT solvers could potentially lead to new and faster algorithms for the TFP problem. Finally, resolving the parameterized complexity of TFP with respect to stronger parameters such as feedback vertex set remains an interesting open problem for future research.

Acknowledgements

The authors wish to thank the anonymous reviewers for their helpful comments and acknowledge support by the European Research Council (ERC) via grant LOPPRE, reference no. 819416, Israel Science Foundation (ISF) grant no. 1176/18 and the Centre for Discrete Mathematics and its Applications, University of Warwick.