Paper deep dive
Nearly Group-Separable Elections
Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski, Kristýna Pekárková, Šimon Schierreich, Ildikó Schlotter
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 9/29/2026, 11:19:16 AM
Summary
This paper investigates the computational complexity of determining how close an election is to various structured preference domains, specifically group-separable (GS), balanced group-separable (GS/bal), and caterpillar group-separable (GS/cat) domains, as well as single-peaked and single-crossing domains. Proximity is measured by the minimum number of adjacent swaps required to transform votes into the target domain. The authors prove that computing this distance is NP-complete for GS/cat (even with 4 voters) and GS/bal domains. However, they develop practical Fixed-Parameter Tractable (FPT) algorithms parameterized by the number of candidates or the swap distance. Notably, an FPT algorithm for swap distance applies to all domains characterized by finite forbidden subelections, resolving an open problem. Experimental results indicate that while ILP formulations are impractical, combinatorial FPT algorithms perform well, and real-world elections are often close to the GS/cat domain.
Entities (10)
Relation Signals (7)
Computing Distance to GS/bal → hascomplexity → NP-complete
confidence 98% · We show that computing the distance from an election to the closest GS/cat or GS/bal one is NP-complete
Computing Distance to GS/cat → hascomplexity → NP-complete
confidence 98% · We show that computing the distance from an election to the closest GS/cat or GS/bal one is NP-complete, for GS/cat even for the case of four voters.
FPT Algorithms → solves → Computing Distance to Domains
confidence 96% · we find practical FPT algorithms parameterized by the number of candidates or swaps.
Group-Separable → hassubdomain → Caterpillar Group-Separable
confidence 95% · The paper discusses GS/cat and GS/bal as subdomains or variants of group-separability defined via PQ-trees.
Group-Separable → hassubdomain → Balanced Group-Separable
confidence 95% · The paper discusses GS/cat and GS/bal as subdomains or variants of group-separability defined via PQ-trees.
FPT Algorithms → appliesto → Domains with Finite Forbidden Subelections
confidence 94% · our algorithm applies to all domains characterized by finite forbidden subelections, resolving a well-established open problem.
Kemeny Aggregation → isequivalentto → Distance to Identity Domain
confidence 90% · In case of the Identity domain, our problem asks for the smallest number of swaps... This is exactly the well-known Kemeny Aggregation problem
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study the problem of computing how close a given election is to being group-separable, measuring proximity by swaps of adjacent candidates in the votes. We also consider several other domains, including caterpillar group-separable, balanced group-separable, single-peaked, and single-crossing ones. Our problem is generally intractable, but we find practical FPT algorithms parameterized by the number of candidates or swaps. For the latter case, our algorithm applies to all domains characterized by finite forbidden subelections, resolving a well-established open problem. We supplement our theoretical findings with experimental analysis.
Tags
Links
- Source: https://arxiv.org/abs/2609.33535v1
- Canonical: https://arxiv.org/abs/2609.33535v1
Trouble viewing inline? Open PDF directly →
Full Text
269,196 characters extracted from source content.
Expand or collapse full text
Nearly Group-Separable Elections Piotr Faliszewski Jan Jabrocki Stanisław Kaźmierowski Kristýna Pekárková Šimon Schierreich Ildikó Schlotter Abstract We study the problem of computing how close a given election is to being group-separable, measuring proximity by swaps of adjacent candidates in the votes. We also consider several other domains, including caterpillar group-separable, balanced group-separable, single-peaked, and single-crossing ones. Our problem is generally intractable, but we find practical FPTFPT algorithms parameterized by the number of candidates or swaps. For the latter case, our algorithm applies to all domains characterized by finite forbidden subelections, resolving a well-established open problem. We supplement our theoretical findings with experimental analysis. 1 AGH University of Krakow, Poland 2 University of Warsaw, Poland 3 Charles University, Czechia 4 Czech Technical University in Prague, Czechia 5 ELTE Centre for Economic and Regional Studies, Hungary 6 Budapest University of Technology and Economics, Hungary faliszew@agh.edu.pl, jjabrocki@student.agh.edu.pl, s.kazmierowski@uw.edu.pl, kristyna.pekarkova@mail.muni.cz, schiesim@fit.cvut.cz, schlotter.ildiko@krtk.elte.hu 1 Introduction An ordinal election consists of a set of candidates and a collection of voters ranking these candidates from the most to the least appealing one: We are interested in computing how close such elections are to being group-separable (GSGS), balanced group-separable (GS/balGS/ ), or caterpillar group-separable (GS/catGS/ ), measuring proximity in terms of the number of swaps of adjacent candidates in the votes. So far, this line of work on election proximity to having structure mostly focused on the single-peaked domain (Faliszewski, Hemaspaandra, and Hemaspaandra 2014; Cornaz, Galand, and Spanjaard 2012; Erdélyi, Lackner, and Pfandler 2017), the single-crossing one (Lakhani, Peters, and Elkind 2019; Jaeckle, Peters, and Elkind 2018), or both of them jointly (Elkind and Lackner 2014; Cornaz, Galand, and Spanjaard 2013). Group-separability also received some attention, but for different notions of distance (Bredereck, Chen, and Woeginger 2016; Kraiczy and Elkind 2022). Group-separability was introduced by Inada (1964); Inada (1969), and is currently receiving increased attention; see, e.g., the works of Karpov (2019); Faliszewski, Karpov, and Obraztsova (2022); Janeczko et al. (2024); Szufa et al. (2025); Boehmer et al. (2022). Inada’s original definition says that an election is group-separable if every subset of its candidates (of size at least two) can be split into two, such that each voter prefers members of one of them to members of the other. Recently, Karpov (2019) provided an alternative definition based on PQ-trees and, using this approach, Faliszewski, Karpov, and Obraztsova (2022) identified its balanced and caterpillar subdomains. The main difference between GS/balGS/ and GS/catGS/ is that the former uses minimum-height trees, whereas the latter uses maximum-height ones. Based on this, Faliszewski, Karpov, and Obraztsova (2022) showed that many problems that are NPNP-hard in general, become polynomial-time solvable for GS/balGS/ elections but remain intractable for GS/catGS/ ones. As tractability under structured domains is the more common behavior, often observed, e.g., for single-peaked and single-crossing domains, this is our first bit of evidence that GS/catGS/ is quite a special domain; for examples of tractability under structured domains, see the survey of Elkind, Lackner, and Peters (2025). The second bit of evidence was provided by Szufa et al. (2025), who have shown that computing Dodgson scores for GS/catGS/ elections using an ILP solver is notably slower than for the other distributions they considered (including those over GS/balGS/ , single-peaked, and single-crossing domains). The third bit was recently provided by Faliszewski et al. (2026a); Faliszewski et al. (2026b), who demonstrated that GS/catGS/ is a surprisingly diverse domain. In particular, they showed that if we draw a vote uniformly at random, then its expected swap distance to the closest GS/catGS/ domain is significantly smaller than to GS/balGS/ , single-peaked, or single-crossing domains. This result strongly relies on the assumption that random votes are completely independent, but since votes in elections are correlated, a priori, it is not clear whether various elections would be closer to being GS/catGS/ , GS/balGS/ , single-peaked, or single-crossing. We want to answer this question, and to do so, we need efficient algorithms to answer such questions. — n m d GSGS ? ? ∗(3m)O^*(3^m) [T4.3] ∗(6d)O^*(6^d) [C4.8] GS/catGS/ NPNP-c [T3.1] para-NPNP-c [T3.1] ∗(2m)O^*(2^m) [T4.4] ∗(8d)O^*(8^d) [C4.8] GS/balGS/ NPNP-c [T3.2] ? ∗((22)m)O^*((2 2)^m) [T4.4] ∗(22d2)O^*(2^2d^2) [T4.9] IdentityIdentity NPNP-c [BTT] para-NPNP-c [DKNS] ∗(2m)O^*(2^m) [BFGNR] ∗(1.53d)O^*(1.53^d) [BFGNR] AntagonismAntagonism NPNP-c [T3.6] para-NPNP-c [T3.6] ∗(2(mlogm))O^*(2^O (m m )) [T4.2] ∗(3.06d)O^*(3.06^d) [T4.10] SeparationSeparation NPNP-c [T3.4] ∗(2n)O^*(2^n) [T3.3] ∗(2m)O^*(2^m) [T4.4] ∗(5d)O^*(5^d) [T4.10] k-Stratificationk- PP (k≤2k≤ 2) [T3.3] para-NPNP-c [T3.5] ∗(3m)O^*(3^m) [T4.4] ∗(3d)O^*(3^d) [T4.10] NPNP-c (k≥3k≥ 3) [T3.4] m/2-Stratification m2- NPNP-c [T3.5] para-NPNP-c [T3.5] ∗(2m)O^*(2^m) [T4.4] ∗(2.84d)O^*(2.84^d) [C4.10] Single-PeakedSingle- NPNP-c [ELP] para-NPNP-c [ELP] ∗(2mlogm)O^*(2^m m) [O4.5] ∗(6d)O^*(6^d) [C4.8] Single-CrossingSingle- NPNP-c [LPE, PB.11] ? ∗(2m2logm)O^*(2^m^2 m) [T4.6] ∗(9d)O^*(9^d) [C4.8] Table 1: An overview of our complexity and algorithmic results. Citations for known results are abbreviated as follows: BFGNR refers to (Betzler et al. 2009), BTT to (Bartholdi I, Tovey, and Trick 1989), DKNS to (Dwork et al. 2001), ELP to (Erdélyi, Lackner, and Pfandler 2017), and LPE to (Lakhani, Peters, and Elkind 2019). Contributions. We show that computing the distance from an election to the closest GS/catGS/ or GS/balGS/ one is NPNP-complete, for GS/catGS/ even for the case of four voters. For GS/balGS/ , such a strong hardness result is elusive, but we give an intuitive explanation as to why this is the case by considering several related domains for which the complexity varies significantly. We circumvent these hardness results by (a) showing reductions to ILP, and giving (b) FPTFPT algorithms parameterized by the number of candidates or the distance from respective domains (see Table 1): 1. We evaluate running times of our algorithms experimentally and, somewhat surprisingly, we find the ILP formulations to be completely impractical. On the positive side, combinatorial FPTFPT algorithms perform very well. 2. One of our algorithms, parameterized by the distance from a domain, applies to all domains characterized by forbidden subelections (such as GSGS, GS/catGS/ , single-peaked and single-crossing ones), resolving the “global swaps” variant of Open Problem 5 of Elkind, Lackner, and Peters (2025), dating back to Erdélyi, Lackner, and Pfandler (2017) and Lakhani, Peters, and Elkind (2019). Experiments show that various elections, including those from the map of elections (Szufa et al. 2025; Faliszewski et al. 2023), are quite close to being GS/catGS/ . Yet, transforming an election to being GS/catGS/ is often more likely to change its winners than transforming it to being GS/balGS/ . Apparently, the former conversions introduce fewer distortions overall, but distort in those parts that matter for winner determination. 2 Preliminaries For k∈ℕk , we let [k]=1,…,k[k]=\1,…,k\. For a finite set X, we write ℒ(X)L(X) to denote the set of all linear orders over X. For a linear order ≻∈ℒ(X) ∈L(X) and a subset Y⊆XY X, the restriction of ≻ to Y, denoted ≻↾Y _ _Y, is the linear order in ℒ(Y)L(Y) in which a precedes b if and only if a≻ba b. Candidates, Votes, and Elections. An election is a pair E=(C,V)E=(C,V), where C is a set of m candidates and V is a set of n voters, where each voter v∈Vv∈ V has a vote ≻v∈ℒ(C) _v∈L(C). To simplify notation, we often write v to refer both to the voter and his or her vote, but the meaning will always be clear. For a vote v∈ℒ(C)v∈L(C) and a candidate c∈Cc∈ C, we write posv(c)pos_v(c) for the position of c in v; the top-ranked candidate has position 11 and the bottom-ranked one has position m. By top(v)=posv−1(1) (v)=pos_v^-1(1) we mean the top-ranked candidate in v. For a set V of voters and a subset C′⊆C C of candidates, by V↾C′V_ _C we mean restricting the votes in V to candidates in C′C . A subelection of E=(C,V)E=(C,V) induced by C′⊆C C and a subset V′V of voters is the election (C′,V↾C′)(C ,V _ _C ), whereas the restriction of E to C′C , written as E↾C′E_ _C , is the subelection induced by C′C and V. Elections E=(C,V)E=(C,V) and E^=(C^,V^) E=( C, V) are isomorphic if they can be made identical by renaming their candidates and voters. An election E E is present in E if there exists a subelection E′E of E that is isomorphic with E E. A voting rule is a function f that given an election outputs a nonempty subset of winning candidates. For example, Plurality outputs the candidates with the highest number of top positions and Borda outputs those with the highest average position. Given an election E=(C,V)E=(C,V), its majority relation is M(E)=(a,b)∈C×C:M(E)=\(a,b)∈ C× C strict majority of voters prefer a to bb\. Copeland rule assigns each candidate c one point for each candidate d such that (c,d)∈M(E)(c,d)∈ M(E) and half a point for each candidate d such that exactly half of the voters prefer c to d; then it outputs the candidates with the highest score. Copeland is Condorcet consistent, i.e., whenever there is a candidate c preferred to every other one by a (possibly different) strict majority of the voters, c is the unique winner. Preference Domains. A (preference) domain D over candidate set C is a non-empty subset of ℒ(C)L(C). The single-peaked domain is among the best-known ones (Black 1948). Definition 2.1. Let axis ⊳ be a linear order over candidate set C. A vote v is single-peaked on ⊳ if for every t∈[|C|]t∈[|C|], its t top-ranked candidates form an interval within ⊳ . A domain D is single-peaked if there exists an axis ⊳∈ℒ(C) ∈L(C) such that D consists of all the votes that are single-peaked on ⊳ . Note that each set of candidates and each axis yields a different single-peaked domain. Consequently, we will often consider families of domains, typically also referring to them as domains. For a (family of) domain(s) X, E is an X election if all its votes belong to (a domain from) X. By (C)X(C) we mean the restriction of X to domains over candidate set C. We primarily consider domains defined using extensions of PQ-trees (Booth and Lueker 1976), following the way in which Karpov (2019) characterized group-separability. To this end, a PQFPQF-tree over a candidate set C=c1,…,cmC=\c_1,…,c_m\ is an ordered rooted tree T with exactly m leaves ℓ1,…,ℓm _1,…, _m, listed from left to right. Each internal node has at least two children and a type that constrains how its children may be permuted: A node of type PP allows arbitrary permutations, a node of type QQ only allows reversals, and a node of type FF fixes the order of the children as is. A mapping φ is a bijection between C and the leaves of T; φ−1(ℓi) ^-1( _i) is the candidate placed at leaf ℓi _i. We also write φ=(φ1,…,φm) =( _1,…, _m) for the sequence of candidates that φ places on the leaves from left to right, so that φi=φ−1(ℓi) _i= ^-1( _i). For a subtree T′T of T with leaf set L′L , let C′C be the set of candidates that φ maps into L′L . The restricted mapping φ↾C′ _ _C is the bijection between C′C and the leaves of T′T obtained by restricting φ to C′C ; read as a sequence, it is the subsequence of (φ1,…,φm)( _1,…, _m) retaining exactly the candidates in C′C . A vote v is consistent with tree T if it is possible to permute the internal nodes’ children—as allowed by their parents’ types—so that reading the leaves from left to right and mapping them according to φ gives exactly this vote. The domain represented by T and φ , denoted (T,φ)D(T, ), is the set of all votes consistent with T. A QQ-tree is a PQFPQF-tree whose all nodes are of type QQ. Let m be the number of candidates. We say that (T,φ)D(T, ) is: • group-separable (GS) if T is a binary QQ-tree; this notion is due to Inada (1964); Inada (1969) but we use the definition of Karpov (2019), see also (Kraiczy and Elkind 2022); • balanced GS (/ GS/ ) if T is a perfect binary QQ-tree, i.e., each leaf is at the same distance from the root;11 1 Some authors allow leaves’ distances from the root to differ by up to 11; this does not affect our experiments as we focus on 8 candidates, but simplifies presentation of our complexity results. • caterpillar GS (/ GS/ ) if T is a binary caterpillar QQ-tree, i.e., every internal node has at least one leaf child; • identity if T has a single internal node of type FF; • antagonism if T has a single internal node of type QQ; • separation if m is even and T’s root is of type QQ with exactly two children, each of type PP and with m/2m/2 leaves. • k-stratification, for k∈[m]k∈[m] with k|mk m, if T’s root is of type FF and has k type-PP children, each with m/km/k leaves. Note that the identity domain contains a single preference order and the antagonism one contains two (which are reversals of each other). We focus on group-separable domains, including its balanced and caterpillar variants. We consider the identity, antagonism, and 22-stratification ones because they are naturally featured on maps of elections (Szufa et al. 2025). Finally, we consider k-stratification domains for larger values of k (in particular, k=m/2k= m2), as well as the separation domain, because they can be viewed as simplified variants of the balanced GS domain (intuitively, m/2-Stratification m2- conflates all but the final two levels of the balanced tree, whereas SeparationSeparation conflates all but the first two). Additionally, we are also interested in single-crossing domains. Definition 2.2 (Mirrlees (1971); Roberts (1977)). A domain over candidate set C is single-crossing if there is an ordering of its votes so that for each two candidates a,b∈Ca,b∈ C, votes that prefer a to b either form a prefix or a suffix of this ordering. We let GSGS, GS/balGS/ , GS/catGS/ , IdentityIdentity, AntagonismAntagonism, k-Stratificationk- , SeparationSeparation, Single-PeakedSingle- , and Single-CrossingSingle- denote families of domains of given types. D is a Condorcet domain if every D election with an odd number of voters has a transitive majority relation. All our domains are Condorcet, except for k-Stratificationk- with k≠m/2k≠ m2 and SeparationSeparation. Election Distance From a Domain. Let u and v be two votes. Their swap distance, denoted dist(u,v)dist(u,v), is the minimum number of swaps of adjacent candidates needed to transform one into the other (equivalently, it is the number of inversions between them). Let E=(C,V)E=(C,V) be an election and let D be a domain over C. Their distance is: dist(E,)=∑v∈Vminu∈dist(u,v),dist(E,D)= _v∈ V\, _u dist(u,v), In other words, it is the number of swaps needed to ensure that all votes from E belong to D. The distance of an election E to a family of domains X, denoted dist(E,)dist(E,X), is its smallest distance to a member of X. Computing this value for various domains is the central problem of this paper. Nearly X Election Given: An election E=(C,V)E=(C,V) and a budget d∈ℕ0d _0. Question: Is dist(E,)≤ddist(E,X)≤ d? For families of domains defined via PQFPQF-trees, the problem asks whether there is a tree T and a mapping φ such that (T,φ)∈D(T, ) and dist(E,(T,φ))≤ddist(E,D(T, ))≤ d; for =Single-PeakedX=Single- , the analogous reformulation quantifies over axes rather than trees. In case of Single-CrossingSingle- , such a reinterpretation is less useful. For the IdentityIdentity domain, our problem asks for the smallest number of swaps of adjacent candidates that ensures that all votes are equal. This is exactly the well-known Kemeny Aggregation problem, i.e., the problem of computing a ranking that minimizes the total swap distance (Kendall-tau distance) to the input rankings (Kemeny 1959). Kemeny Aggregation Given: An election (C,V)(C,V) and a budget d∈ℕ0d _0. Question: Does there exist a vote u∗u^* over C such that ∑v∈Vdist(v,u∗)≤d _v∈ Vdist(v,u^*)≤ d? Bartholdi I, Tovey, and Trick (1989) showed that the Kemeny Aggregation problem is NP-hard, while Hemaspaandra, Spakowski, and Vogel (2005) established its exact complexity. This intractability has motivated approximation algorithms (Ailon, Charikar, and Newman 2008), parameterized algorithms (Betzler and Dorn 2010; Betzler, Bredereck, and Niedermeier 2014), and heuristic approaches (Conitzer, Davenport, and Kalagnanam 2006). Moreover, even verifying whether a given ranking is Kemeny-optimal is coNPcoNP-hard (Fitzsimmons and Hemaspaandra 2021). 3 Hardness of Finding Distances to Domains Our goal in this section is to establish the hardness of Nearly X Election for our domains. Note that it is in NPNP for all of the above-defined domains (see Proposition B.2). Intractability for GS/cat and GS/bal. We first show that Nearly GS/catGS/ Election is NPNP-complete, via a reduction from Kemeny Aggregation. Our proof relies on the observation that if two votes u and v belong to the same GS/catGS/ domain and rank the same two candidates at the bottom, but in opposite order, then they must rank all the preceding candidates identically. Together with another technical trick, this ensures that finding the closest GS/catGS/ election boils down to making (large parts of) all the votes identical, as in Kemeny Aggregation. As our reduction preserves the number of voters, we inherit hardness for the case of four voters. Theorem 3.1 (⋆ ). Nearly GS/catGS/ Election is NPNP-complete, even for elections with 44 voters. For the case of GS/balGS/ , we also obtain NPNP-completeness, but in this case the proof is far more involved, and follows by a reduction from the Maximum Vertex Coverage problem on bipartite graphs, shown to be NPNP-hard independently by Apollonio and Simeone (2014) and Joret and Vetta (2015). Theorem 3.2 (⋆ ). Nearly GS/balGS/ Election is NPNP-complete. Unfortunately, in this case we do not get hardness for a constant number of voters and seeking such a result, or an XP algorithm, is an interesting challenge. We justify this view by considering several domains that capture different aspects of GS/balGS/ and yield quite different complexity results. Stratification and Separation. 2-Stratification2- consists of votes over even-sized candidate sets, where half of the candidates always precede those in the other half, but without any other restrictions. This captures the basic feature of GS/balGS/ that candidates are split into two groups, but (a) it only includes the top-level split, and (b) GS/balGS/ allows reversing the order of the two groups whereas 2-Stratification2- does not. If we do allow this reversing, then we obtain the SeparationSeparation domain. While these domains are rather basic, they do have some interesting algorithmic features. Theorem 3.3 (⋆ ). There is a polynomial-time algorithm for Nearly 2-Stratification2- Election and an FPTFPT algorithm for Nearly SeparationSeparation Election, parameterized by n. The FPTFPT algorithm for SeparationSeparation guesses which votes to reverse and runs the algorithm for 2-Stratification2- , which itself partitions the candidates based on their average positions (i.e., Borda scores). Unfortunately, this approach does not generalize and already for 3-Stratification3- we obtain NPNP-completeness (but not para-NPNP-completeness). We also show NPNP-completeness for the SeparationSeparation domain. Theorem 3.4 (⋆ ). Nearly 3-Stratification3- Election and Nearly SeparationSeparation Election are NPNP-complete. Yet, for m/2-Stratification m2- , where m is the number of candidates, we do obtain para-NPNP-completeness. Here, as in GS/balGS/ , there are pairs of adjacent candidates that we can freely swap, but we cannot make any other swaps. Theorem 3.5 (⋆ ). Nearly m/2-Stratification m2- Election is NPNP-complete, even for elections with 44 voters. Antagonism. Each domain in the AntagonismAntagonism family consists of two votes, each being a reverse of the other one. Hence, Nearly AntagonismAntagonism Election is very similar to Kemeny Aggregation and we easily inherit its hardness. Theorem 3.6 (⋆ ). Nearly AntagonismAntagonism Election is NPNP-complete, even for elections with 44 voters. GS. Unfortunately, we were not able to establish the exact complexity of Nearly GSGS Election. On the one hand, we face similar difficulties as for GS/balGS/ and parameterization by the number of voters, but even more importantly, all our previous domains were defined via trees of a single “shape,” whereas here we have many different possibilities. 4 Algorithmic Results One of the most practical ways of solving NPNP-complete problems is by reducing them to integer linear programming (ILP). Doing so is, indeed, possible in our case but, somewhat surprisingly, in Section 5 we will see that our ILPs are fairly slow to solve by modern solvers. Theorem 4.1. Given an election with m candidates and n voters, there is a polynomial-time reduction of Nearly X Election, ∈GS/cat,GS/balX∈\GS/ ,GS/ \, to Integer Linear Programming with (nm2)O(nm^2) variables and (m3+nm2)O(m^3+nm^2) constraints if =GS/catX=GS/ , and (nm2logm)O(nm^2 m) variables and ((n+logm)⋅m2logm)O((n+ m)· m^2 m) constraints if =GS/balX=GS/ . Consequently, we seek direct, combinatorial FPTFPT algorithms, parameterized either by the number of candidates or the distance from the given domain. 4.1 Parameter: Number of Candidates In case of parameterization by the number m of candidates, the baseline idea is to perform a brute-force search over all trees and mappings. This yields ∗(2mlogm)O^* (2^m m ) running time. Theorem 4.2 (⋆ ). For each of our families of domains defined by PQFPQF-trees, there is an FPTFPT algorithm for Nearly X Election when parameterized by the number of candidates. Using dynamic programming, we obtain substantially faster algorithms. In particular, for GSGS, the underlying idea is to build the PQFPQF tree of the closest (T,φ)D(T, ) domain bottom-up, at each node counting only the swaps required to ensure that the voters rank candidates from one subtree ahead (or behind) those from the other subtree. Consequently, for each node and each candidate, we need to know if this candidate appears in this node and, if so, if it belongs to the left or the right subtree. This requires ∗(3m)O^* (3^m ) time. Theorem 4.3 (⋆ ). There is an algorithm solving Nearly GSGS Election in (3m⋅mn)O (3^m· mn ) time. For other domains, variants of this algorithm are even faster. Theorem 4.4 (⋆ ). Nearly X Election can be solved in (2m⋅mn)O (2^m· mn ) time if =GS/cat,Separation,m/2-StratificationX=\GS/ ,Separation, m2- \, ((22)m⋅mn)O ((2 2)^m· mn ) time if =GS/balX=GS/ , and (3m⋅mn)O (3^m· mn ) time if =k-StratificationX=k- , for every k. We conclude with our domains that cannot be defined using PQFPQF-trees. For a single-peaked election, there is a trivial brute-force algorithm trying all possible axes ⊳ . Observation 4.5 (⋆ ). Nearly Single-PeakedSingle- Election can be solved in 2(m⋅logm)⋅n2^O (m· m )· n time. For the single-crossing domain, the argument is not as straightforward; however, it follows a similar strategy. In particular, we prove that it is enough to focus only on the maximal single-crossing domains (Puppe and Slinko 2019). Theorem 4.6 (⋆ ). The Nearly Single-CrossingSingle- Election problem can be solved in 2(m2⋅logm)⋅n2^O (m^2· m )· n time. 4.2 Parameter: Distance to a Domain For the parameterization by the distance to a domain, we obtain a general algorithm that applies to a wide class of domains, including many of ours, but we need some additional terminology and notation before presenting it. A domain D is hereditary, if for every election E∈E , all subelections of E belong to D (restricted to a given set of candidates). It is known that every hereditary domain can be characterized by a (possibly infinite) set ℱF of forbidden subelections (Lackner and Lackner 2017). In fact, a more concise characterization is obtained through a family of forbidden partial subelections, each of them a pair (C⋆,V⋆)(C ,V ) where C⋆C is a set of candidates and V⋆V is a collection of partial votes, i.e., partial orders over C⋆C . We assume that each partial vote v∈V⋆v∈ V is given as a set PvP_v of pairs (a,b)(a,b) for which a≻vba _vb and there exists no c∈C⋆c∈ C with a≻vc≻vba _vc _vb. The size of a partial subelection (C⋆,V⋆CLOSE(C ,V ) is ∑v∈V⋆|Pv| _v∈ V |P_v|. A domain D is characterized by a set ℱF of forbidden partial subelections if any election E belongs to D exactly if there is no (C⋆,V⋆)∈ℱ(C ,V ) whose linear extension is present in E. Theorem 4.7 (⋆ ). Let D be a domain characterized by a family ℱF of forbidden partial subelections, each with at most γ candidates and of size at most σ. Then Nearly D Election can be solved in (max(2,σ)d⋅|ℱ|⋅mγ+1n)O ( (2,σ)^d·|F|· m^γ+1n ) time. The algorithm is a bounded-search-tree exploration of the search space. We start with an election E=(C,V)E=(C,V) and we maintain for each voter vi∈Vv_i∈ V a set RiR_i of committed inversions, that is, pairs of candidates whose relative order in the sought election must be the opposite of their order in viv_i. We call an election admissible for ℛR if, for each i∈[n]i∈[n], its i-th vote inverts all pairs in RiR_i relative to viv_i. We consider ℛ=(R1,…,Rn)R=(R_1,…,R_n) the state of the algorithm; initially, all sets RiR_i are empty. We describe how to compute a value f(ℛ)f(R), for each state ℛR, defined as the minimum swap distance between E and an election in D admissible for ℛR if this distance is at most d, and ∞ otherwise. Since the swap distance of two votes equals the number of pairs of candidates on which they disagree, every election admissible for ℛR is at swap distance at least ∑i|Ri| _i|R_i| from E. Thus, the algorithm sets f(ℛ)=∞f(R)=∞ whenever ∑i|Ri|>d _i\!|R_i|>d. Assume the algorithm is in a state ℛR with ∑i|Ri|≤d _i|R_i|≤ d. For each voter viv_i, we build the tournament TiT_i obtained from viv_i by reversing exactly the arcs corresponding to the pairs in RiR_i. If some TiT_i contains a directed triangle, we set f(ℛ)=∞f(R)=∞ in case all three arcs of the triangle belong to RiR_i, and otherwise we branch by adding to RiR_i each of the (at most two) pairs of the triangle outside RiR_i and set f(ℛ)=minf(ℛ′)f(R)= f(R ) where the minimum is taken over all states ℛ′R resulting from the branching. If every tournament TiT_i is acyclic, it is transitive and admits a unique linear extension v^i v_i. We let E^=(C,(v^1,…,v^n)) E=(C,( v_1,…, v_n)). If E^∈ E , we set f(ℛ)=∑i|Ri|f(R)= _i|R_i|. Otherwise, we find some (C⋆,V⋆)∈ℱ(C ,V ) present in E E; in particular, for every injection π:C⋆→Cπ:C → C and each partial vote v∈V⋆v∈ V we search for a vote φ(v)∈v^1,…,v^n (v)∈\ v_1,…, v_n\ that extends the partial vote obtained from v by replacing each candidate c∈C⋆c∈ C with π(c)π(c). Note that this can be done in |ℱ|⋅mγ⋅(mn)|F|· m^γ·O(mn) time. We branch over all voters vi∈φ(v):v∈V⋆v_i∈\ (v) v∈ V \ and over all pairs (a,b)∈Pφ−1(vi)(a,b)∈ P_ ^-1(v_i) for which π(a),π(b)\π(a),π(b)\ is not a committed inversion in RiR_i; in the branch corresponding to viv_i and (a,b)(a,b), we add π(a),π(b)\π(a),π(b)\ to RiR_i. We return f(ℛ)=minf(ℛ′)f(R)= f(R ) where the minimum is taken over all states ℛ′R obtained in some branch. Every branch adds a new pair to some RiR_i, so ∑i|Ri| _i|R_i| strictly increases along every branch. Moreover, the recursion terminates when ∑i|Ri| _i|R_i| exceeds d. The algorithm starts in state ℛ0=(∅,…,∅)R_0=( ,…, ) and returns yes if and only if f(ℛ0)f(R_0) is finite. We prove the correctness of the algorithm in Section D.1. There are at most two branches in each triangle-resolution branching and at most ∑v∈V⋆|Pv| _v∈ V |P_v| branches in each branching that results from finding a forbidden partial subelection in E E; therefore, the number of branches in such a case is at most the size of this partial subelection and, hence, at most σ. Each branch adds a new committed inversion, and states with ∑i|Ri|>d _i|R_i|>d are pruned, so the depth of the search tree is at most d. Hence, starting from ℛ0=(∅,…,∅)R_0=( ,…, ), we obtain a search tree of size (max(2,σ)d)O ( (2,σ)^d ), and in each state we spend |ℱ|⋅mγ⋅(mn)|F|· m^γ·O(mn) time for building the tournaments, detecting directed triangles, and finding a forbidden partial subelection (or detecting that E E belongs to D). This proves the theorem. It is known that both the Single-PeakedSingle- and the GSGS domains can be characterized by a family of forbidden partial subelections, each of size 66 (Ballester and Haeringer 2011). Moreover, the GS/catGS/ domain is characterized by a family of forbidden partial subelections, one of size 88 and the rest of size 66 (Kraiczy and Elkind 2022). The Single-CrossingSingle- domain is characterized by two forbidden partial subelections, one of size 88 and the other of size 99 (Bredereck, Chen, and Woeginger 2013). Hence, we have the following corollary. Corollary 4.8. Nearly X Election can be solved in • 6d⋅(mn)(1)6^d·(mn)^O (1 ) time if ∈Single-Peaked,GSX∈\Single- ,GS\; • 8d⋅(mn)(1)8^d·(mn)^O (1 ) time if =GS/catX=GS/ ; • 9d⋅(mn)(1)9^d·(mn)^O (1 ) time if =Single-CrossingX=Single- . We remark that we also developed an algorithm tailored directly to the GSGS domain; see Section D.2. We also provide a specialized algorithm for GS/catGS/ , which relies on the observation that in a GS/catGS/ election there is a candidate that is always ranked first or last. The algorithm guesses this candidate, moves him or her to the closer end of each vote, removes it from consideration and repeats the process. A similar in spirit approach also works for GS/balGS/ , sidestepping the fact that it is not hereditary. Theorem 4.9 (⋆ ). Nearly GS/catGS/ Election can be solved in 2(d⋅logd)⋅(mn)(1)2^O (d· d )·(mn)^O (1 ) time, and Nearly GS/balGS/ Election can be solved in 2(d2)⋅(mn)(1)2^O (d^2 )·(mn)^O (1 ) time. For domains with a simpler structure, a more direct approach—using branching but no recursive decomposition—offers FPT algorithms with a better dependence on the parameter d. For AntagonismAntagonism (and IdentityIdentity), which are hereditary (see Proposition D.17 in Appendix D) we could have applied Theorem 4.7, but the algorithm would be slower. Theorem 4.10 (⋆ ). Nearly X Election can be solved in • 3d⋅(mn)3^d·O (mn ) time if =k-StratificationX=k- , for every k; • 2.832d⋅(mn)2.832^d·O (mn ) time if =m/2-StratificationX=m/2- ; • 5d⋅(mn)5^d·O (mn ) time if =SeparationX=Separation; • 3.06d⋅(mn)3.06^d·O (mn ) time if =AntagonismX=Antagonism. 5 Experiments We consider three main questions: (a) How fast are our algorithms in practice? (b) How close are various elections to being (caterpillar/balanced) group-separable? (c) How likely are closest GSGS elections to retain the original winners? The latter two questions evaluate similarity of the source and derived elections, either on the level of individual swaps or on the level of features relevant for voting rules. Following the map framework of Szufa et al. (2025), we focus on synthetic data, specifically using the setting of Faliszewski et al. (2023); see these works, and the survey of Boehmer et al. (2024), for details on generating elections. Here we provide high-level intuitions regarding our models: • In the normalized Mallows model (NM-ϕφ) each vote is derived from a fixed central one, by introducing random swaps of candidates, driven by the value of the ϕφ parameter (Mallows 1957; Boehmer, Faliszewski, and Kraiczy 2023); ϕ=1φ=1 means that, in effect, the resulting vote is chosen uniformly at random (this is also known as Impartial Culture; IC) and smaller values of ϕφ mean proportionally fewer swaps (for ϕ=0φ=0 no swaps are made and all votes are equal to the central one). • In the Pólya–Eggenberger urn model (URN-α) we have several different-sized clusters of votes. All the votes in a single cluster are identical, chosen uniformly at random. The larger the α parameter, the fewer clusters there are (Berg 1985; McCabe-Dansted and Slinko 2006) • In the ttD-Euclidean model (EUC-ttD) candidates and voters are points drawn uniformly at random from [0,1]t[0,1]^t; the voters rank the candidates from the closest to the farthest to them (in terms of the Euclidean distance). We also consider elections generated by drawing votes uniformly at random from the GSGS, GS/catGS/ , and GS/balGS/ domains, from the single-peaked (Walsh 2015; Conitzer 2009) and single-crossing (Szufa et al. 2025) distributions. Following Faliszewski et al. (2023), we focus on the setting with 88 candidates and 9696 voters. All experiments were performed on a machine equipped with two 6464-core AMD EPYC 7742 CPUs and 512512 GB of RAM. All implementations are in Python and use the Prefsampling library (Boehmer et al. 2024). We used the Gurobi Optimizer, version 13.0.1. (a) Running times of our algorithms for the Nearly GS/catGS/ Election problem on NM-ϕφ elections with 9696 voters, for different numbers of candidates and different values of ϕφ. (b) Map of synthetic elections with 88 candidates and 9696 voters, and their GSGS projections (pointed to by the arrows). Colors represent the per-voter distances to the projections. (c) Fractions of elections (|C|=8|C|=8, |V|=96|V|=96, sampled from given models) for which GS/catGS/ , GS/balGS/ , GSGS, and Single-PeakedSingle- projections are closest (among these four). Figure 1: Results of our numerical experiments. 5.1 Algorithms Running Time Due to limited space, for running-time analysis we focus on GS/catGS/ ; our results are most varied and most interesting in this case. We compare the brute-force algorithm (trying all possible mappings φ between C and leaves(T)leaves(T)), the FPTFPT algorithm parameterized by the number of candidates m (Theorem 4.4), two FPTFPT algorithms parameterized by the distance d—the algorithm tailored to the GS-caterpillar domain (Theorem 4.9), denoted FPT(d) $FPT$(d), and the general algorithm for domains characterized by forbidden partial subelections (Corollary 4.8), denoted FPT(d) $FPT$(d)-subelections—and the ILP formulation of the problem (Appendix F). For an analogous analysis regarding other domains, see Section E.1. For each number of candidates m in 2,…,20\2,…,20\ and each ϕ∈0.0,0.1,0.3,0.5,0.7,0.9φ∈\0.0,0.1,0.3,0.5,0.7,0.9\, we attempted to run each of our algorithms on 10001000 elections sampled from ϕφ-NM, with 96 voters. If an algorithm did not complete within 1515 minutes, we terminated it and did not run it for larger numbers of candidates. We plot the averages of the obtained running times in Figure 1(a) (log scale), with the range between the first and the third quartile highlighted by a shaded bar, and the minimum and maximum values marked by ticks. Barring small values of ϕφ, the FPT(m) $FPT$(m) algorithm performed best, whereas the FPT(d) $FPT$(d)-subelections performed worst, losing even to the trivial brute-force one. The FPT(d) $FPT$(d) algorithm performed far better and was the closest to challenging the FPT(m) $FPT$(m) one. Intuitively, this difference between the theoretical and experimental results stems from the fact that the FPT(d) $FPT$(d)-subelections algorithm decreases the value of the parameter by 11 in each recursive call, whereas the FPT(d) $FPT$(d) may decrease it even by numbers proportional to the number of voters (indeed, one might suspect that it is even FPTFPT with respect to the average number of swaps per voter, but we have not been able to prove this). Finally, we note that our ILP-based algorithms perform poorly, which is surprising given how effective this approach usually is. 5.2 Distance from a Structured Domain Briefly put, a map of elections is a visualization of an election dataset so that each election is a dot on a 2D plane and the closer two dots are, the fewer swaps of adjacent candidates are needed to make the respective elections isomorphic; see, e.g., the works of Szufa et al. (2025) and Faliszewski et al. (2023). The map also includes three special points: identity (ID), representing elections were all votes are equal, antagonism (AN), representing elections where voters are split into two halves, where each half has identical votes that are reverses of those in the other half, and uniformity (UN), representing elections with all possible votes. We show our map in Figure 1(b), containing 10 elections for each of the synthetic models we considered (with 88 candidates and 9696 voters); for each of these original elections we computed the closest GSGS election, called its projection, and also included it on the map, with an arrow pointing from the original one to the projection. Each original election is colored by the number of swaps (per voter) needed to obtain its projection. Each projection is colored according to its type. We note that it suffices to make fewer than 55 swaps of adjacent candidates (per voter) to transform any of our elections to its projection. The largest possible swap distance between two votes with 88 candidates is 2828, so all our elections are at a modest distance from having GSGS structure. Second, there is a clear separation between elections projected to GS/catGS/ ones and the remaining ones. Specifically, the former have less internal structure (and, hence, are closer to IC) and the latter are structured in one way or another; e.g., are close to ID, are single-peaked (SP), single-crossing (SC), or are Euclidean (EUC). Third, the projections are systematically located in a particular neighborhood of their originals (often in the direction of AN, suggesting increased polarization). While the map gives an intuitive overview, we also performed a more statistically significant study. For several models, we have sampled 10001000 elections and computed their closest GS/catGS/ , GS/balGS/ , and GSGS elections, as well as the closest single-peaked ones, as an external reference point. In Figure 1(c), we show which fractions of elections from a given culture are closest to each of these domains (GSGS gets “a point” only if neither a GS/catGS/ nor a GS/balGS/ election was closest to the considered one; any remaining ties split the point equally among the tied domains). A more detailed overview with particular numerical values is available in Table 3. The general conclusions are the same as in the case of the map, with the additional observation that single-peaked elections are closest to NM-ϕφ ones with ϕ≤0.5φ≤ 0.5. In Section E.2, we also provide a similar analysis of real-life elections from PrefLib (Mattei and Walsh 2013). 5.3 Retaining Winners Figure 2: Probability of retaining winners (being successful) for GS/catGS/ , GS/balGS/ , GSGS, and Single-PeakedSingle- projections. Finally, we checked how likely the projections are to retain the same winners as the original elections. To maintain focus, we considered Plurality, Borda, and Copeland voting rules. For each of the considered models, i.e., for NM-ϕφ, EUC-ttD, SC, and URN-α, we have sampled 200200 elections (with 88 candidates and 9696 voters), computed their closest GS/catGS/ , GS/balGS/ , GSGS, and single-peaked elections, and computed the winners according to each of our rules. Since the rules can output sets of winners, we refer to a projection as successful if it shares at least one of the winners with the original election. Further, it is possible that there are several closest elections of a given type to a given original one, each with a possibly different set of winners. In Figure 2, we report the probabilities that the closest election of a given type is successful; additionally, the top line gives the probability that at least one of the projections is successful, and the bottom line gives the probability that all projections are successful. Overall, our projections are successful with probability at least 50%50\%, and the more structured the original election is, the higher the chance of success. That said, GS/catGS/ projections are least likely to be successful (except for the Borda rule, where they typically are on par with other domains). GS/balGS/ projections perform best for Copeland, average for Plurality, and either average or worst for Borda. Single-peaked projections are the best for Plurality and perform well overall. 6 Conclusions We have found that many (synthetic) elections (with 8 candidates and 96 voters) are close to being group-separable (GS). Further, the less structured they are, the more likely their closest GS elections are caterpillar. Yet, it was the GS/balGS/ elections that maintained the high-level features of the original elections best, maintaining the same winners most frequently. To obtain these results, we have designed a number of algorithms computing closest structured elections, solving Open Problem 5 of Elkind, Lackner, and Peters (2025). Acknowledgments This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 101002854), was co-funded by the European Union under the project Robotics and Advanced Industrial Production (reg. no. CZ.02.01.01/00/22_008/0004590), and supported in part by the National Science Centre, Poland, grant number UMO-2025/58/A/ST6/00371. References Ailon, Charikar, and Newman (2008) Ailon, N.; Charikar, M.; and Newman, A. 2008. Aggregating Inconsistent Information: Ranking and Clustering. Journal of the ACM, 55(5). Apollonio and Simeone (2014) Apollonio, N.; and Simeone, B. 2014. The Maximum Vertex Coverage Problem on Bipartite Graphs. Discrete Applied Mathematics, 165: 37–48. Bachmeier et al. (2019) Bachmeier, G.; Brandt, F.; Geist, C.; Harrenstein, P.; Kardel, K.; Peters, D.; and Seedig, H. G. 2019. k-Majority Digraphs and the Hardness of Voting With a Constant Number of Voters. Journal of Computer and System Sciences, 105: 130–157. Ballester and Haeringer (2011) Ballester, M. A.; and Haeringer, G. 2011. A Characterization of the Single-Peaked Domain. Social Choice and Welfare, 36: 305–322. Bartholdi I, Tovey, and Trick (1989) Bartholdi I, J. J.; Tovey, C. A.; and Trick, M. A. 1989. The Computational Difficulty of Manipulating an Election. Social Choice and Welfare, 6: 227–241. Berg (1985) Berg, S. 1985. Paradox of Voting Under an Urn Model: The Effect of Homogeneity. Public Choice, 47(2): 377–387. Betzler, Bredereck, and Niedermeier (2014) Betzler, N.; Bredereck, R.; and Niedermeier, R. 2014. Theoretical and Empirical Evaluation of Data for Exact Kemeny Rank Aggregation. Autonomous Agents and Multi-Agent Systems, 28: 721–748. Betzler and Dorn (2010) Betzler, N.; and Dorn, B. 2010. Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules. Journal of Computer and System Sciences, 76(8): 812–836. Betzler et al. (2009) Betzler, N.; Fellows, M. R.; Guo, J.; Niedermeier, R.; and Rosamond, F. A. 2009. Fixed-Parameter Algorithms for Kemeny Rankings. Theoretical Computer Science, 410(45): 4554–4570. Bjorner and Brenti (2005) Bjorner, A.; and Brenti, F. 2005. Combinatorics of Coxeter Groups, volume 231 of Graduate Texts in Mathematics. Berlin, Heidelberg: Springer. ISBN 978-3-540-44238-7. Black (1948) Black, D. 1948. On the Rationale of Group Decision-Making. Journal of Political Economy, 56(1): 23–34. Boehmer et al. (2022) Boehmer, N.; Bredereck, R.; Elkind, E.; Faliszewski, P.; and Szufa, S. 2022. Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning. In Proceedings of NIPS-2022, 31347–31359. Red Hook, NY, USA: Curran Associates. Boehmer et al. (2024) Boehmer, N.; Faliszewski, P.; Janeczko, Ł.; Kaczmarczyk, A.; Lisowski, G.; Pierczyński, G.; Rey, S.; Stolicki, D.; Szufa, S.; and Wąs, T. 2024. Guide to Numerical Experiments on Elections in Computational Social Choice. In Proceedings of IJCAI-2024, 7962–7970. ijcai.org. Boehmer, Faliszewski, and Kraiczy (2023) Boehmer, N.; Faliszewski, P.; and Kraiczy, S. 2023. Properties of the Mallows Model Depending on the Number of Alternatives: A Warning for an Experimentalist. In Proceedings of ICML-2023, 2689–2711. Cambridge, MA, USA: PMLR. Booth and Lueker (1976) Booth, K. S.; and Lueker, G. S. 1976. Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms. Journal of Computer and System Sciences, 13(3): 335–379. Bredereck, Chen, and Woeginger (2013) Bredereck, R.; Chen, J.; and Woeginger, G. J. 2013. A Characterization of the Single-Crossing Domain. Social Choice and Welfare, 41: 989–998. Bredereck, Chen, and Woeginger (2016) Bredereck, R.; Chen, J.; and Woeginger, G. J. 2016. Are There Any Nicely Structured Preference Profiles Nearby? Mathematical Social Sciences, 79: 61–73. Conitzer (2009) Conitzer, V. 2009. Eliciting Single-Peaked Preferences Using Comparison Queries. Journal of Artificial Intelligence Research, 35(1): 161–191. Conitzer, Davenport, and Kalagnanam (2006) Conitzer, V.; Davenport, A.; and Kalagnanam, J. 2006. Improved Bounds for Computing Kemeny Rankings. In Proceedings of AAAI-2006, 620–626. Menlo Park, CA, USA: AAAI Press. Cornaz, Galand, and Spanjaard (2012) Cornaz, D.; Galand, L.; and Spanjaard, O. 2012. Bounded Single-Peaked Width and Proportional Representation. In Proceedings of ECAI-2012, volume 242 of FAIA, 270–275. Amsterdam, Netherlands: IOS Press. Cornaz, Galand, and Spanjaard (2013) Cornaz, D.; Galand, L.; and Spanjaard, O. 2013. Kemeny Elections with Bounded Single-Peaked or Single-Crossing Width. In Proceedings of IJCAI-2013, 76–82. Palo Alto, CA, USA: AAAI Press. Dwork et al. (2001) Dwork, C.; Kumar, R.; Naor, M.; and Sivakumar, D. 2001. Rank Aggregation Methods for the Web. In Proceedings of W-01, 613–622. New York, NY, USA: ACM. Elkind and Lackner (2014) Elkind, E.; and Lackner, M. 2014. On Detecting Nearly Structured Preference Profiles. In Proceedings of AAAI-2014, 661–667. Palo Alto, CA, USA: AAAI Press. Elkind, Lackner, and Peters (2025) Elkind, E.; Lackner, M.; and Peters, D. 2025. Preference Restrictions in Computational Social Choice: A Survey. arXiv:2205.09092. Erdélyi, Lackner, and Pfandler (2017) Erdélyi, G.; Lackner, M.; and Pfandler, A. 2017. Computational Aspects of Nearly Single-Peaked Electorates. Journal of Artificial Intelligence Research, 58: 297–337. Faliszewski, Hemaspaandra, and Hemaspaandra (2014) Faliszewski, P.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2014. The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates. Artificial Intelligence, 207: 69–99. Faliszewski et al. (2023) Faliszewski, P.; Kaczmarczyk, A.; Sornat, K.; Szufa, S.; and Wąs, T. 2023. Diversity, Agreement, and Polarization in Elections. In Proceedings of IJCAI-2023, 2684–2692. ijcai.org. Faliszewski, Karpov, and Obraztsova (2022) Faliszewski, P.; Karpov, A.; and Obraztsova, S. 2022. The Complexity of Election Problems With Group-Separable Preferences. Autonomous Agents and Multi-Agent Systems, 36. Faliszewski et al. (2026a) Faliszewski, P.; Sornat, K.; Szufa, S.; and Wąs, T. 2026a. Diversity of Structured Domains via k-Kemeny Scores. In Proceedings of AAAI-2026, 16880–16888. Washington, DC, USA: AAAI Press. Faliszewski et al. (2026b) Faliszewski, P.; Sornat, K.; Szufa, S.; and Wąs, T. 2026b. Outer Diversity of Structured Domains. In Proceedings of AAMAS-2026, 2106–2114. Richland, SC, USA: IFAAMAS. Fitzsimmons and Hemaspaandra (2021) Fitzsimmons, Z.; and Hemaspaandra, E. 2021. Kemeny Consensus Complexity. In Proceedings of IJCAI-2021, 196–202. ijcai.org. Hemaspaandra, Spakowski, and Vogel (2005) Hemaspaandra, E.; Spakowski, H.; and Vogel, J. 2005. The Complexity of Kemeny Elections. Theoretical Computer Science, 349(3): 382–391. Inada (1964) Inada, K. 1964. A Note on the Simple Majority Decision Rule. Econometrica, 32(4): 525–531. Inada (1969) Inada, K. 1969. The Simple Majority Decision Rule. Econometrica, 37(3): 490–506. Jaeckle, Peters, and Elkind (2018) Jaeckle, F.; Peters, D.; and Elkind, E. 2018. On Recognising Nearly Single-Crossing Preferences. In Proceedings of AAAI-2018, 1079–1086. Palo Alto, CA, USA: AAAI Press. Janeczko et al. (2024) Janeczko, Ł.; Lang, J.; Lisowski, G.; and Szufa, S. 2024. Discovering Consistent Subelections. In Proceedings of AAMAS-2024, 935–943. Richland, SC, USA: IFAAMAS. Joret and Vetta (2015) Joret, G.; and Vetta, A. 2015. Reducing the Rank of a Matroid. Discrete Mathematics & Theoretical Computer Science, 17(2): 143–156. Karpov (2019) Karpov, A. 2019. On the Number of Group-Separable Preference Profiles. Group Decision and Negotiation, 28: 501–517. Kemeny (1959) Kemeny, J. G. 1959. Mathematics Without Numbers. Daedalus, 88(4): 577–591. Kraiczy and Elkind (2022) Kraiczy, S.; and Elkind, E. 2022. Explaining Preferences by Multiple Patterns in Voters’ Behavior. In Proceedings of IJCAI-2022, 370–376. ijcai.org. Kuo and Fuchs (1987) Kuo, S.; and Fuchs, W. K. 1987. Efficient Spare Allocation in Reconfigurable Arrays. IEEE Design & Test of Computers, 4(1): 24–31. Lackner and Lackner (2017) Lackner, M.; and Lackner, M. 2017. On the Likelihood of Single-Peaked Preferences. Social Choice and Welfare, 48: 717–745. Lakhani, Peters, and Elkind (2019) Lakhani, F.; Peters, D.; and Elkind, E. 2019. Correlating Preferences and Attributes: Nearly Single-Crossing Profiles. In Proceedings of IJCAI-2019, 414–420. ijcai.org. Mallows (1957) Mallows, C. L. 1957. Non-null Ranking Models. Biometrica, 44(1/2): 114–130. Mattei and Walsh (2013) Mattei, N.; and Walsh, T. 2013. PrefLib: A Library for Preferences. In Proceedings of ADT-2013, volume 8176 of LNCS, 259–270. Berlin, Heidelberg: Springer. McCabe-Dansted and Slinko (2006) McCabe-Dansted, J. C.; and Slinko, A. 2006. Exploratory Analysis of Similarities Between Social Choice Rules. Group Decision and Negotiation, 15: 77–107. Mirrlees (1971) Mirrlees, J. A. 1971. An Exploration in the Theory of Optimal Income Taxation. The Review of Economic Studies, 38(2): 175–208. Puppe and Slinko (2019) Puppe, C.; and Slinko, A. 2019. Condorcet Domains, Median Graphs and the Single-Crossing Property. Economic Theory, 67: 285–318. Roberts (1977) Roberts, K. W. 1977. Voting Over Income Tax Schedules. Journal of Public Economics, 8(3): 329–340. Szufa et al. (2025) Szufa, S.; Boehmer, N.; Bredereck, R.; Faliszewski, P.; Niedermeier, R.; Skowron, P.; Slinko, A.; and Talmon, N. 2025. Drawing a Map of Elections. Artificial Intelligence, 343. Walsh (2015) Walsh, T. 2015. Generating Single Peaked Votes. arXiv:1503.02766. Appendix A Additional Notation Here we provide additional notation that we subsequently use in our proofs. When defining votes in an election, we may write a vote v=(c1,…,cm)v=(c_1,…,c_m) in the form v:c1,…,cm.v:c_1,…,c_m. Such preference lists can also include sets; the interpretation of this is that the candidates in these sets are ordered in an arbitrarily fixed way. Often, we implicitly assume some arbitrary, fixed ordering ≻ over the candidate set; then, for a set S of candidates, we denote by S→ S the sequence of the candidates in S ordered according to ≻ , and we denote by S← S the reverse of this sequence. We say that an election E=(C,V)E=(C,V) is caterpillar-consistent if there exists a caterpillar tree T and a mapping φ such that every vote v∈Vv∈ V belongs to (T,φ)D(T, ). If the number m of candidates is clear from the context, then we will denote by TcatT^cat the caterpillar tree that has m leaves, each a left child. Some of our algorithms will use a branching method where we guess certain values or some property of the solution; the interpretation of such a guessing step is that the algorithm exhaustively tries all possibilities. Finally, we also adopt the conventions a+∞=∞a+∞=∞ and min∅=∞ =∞. Appendix B Additional material for Section 3 In this section, we present in detail our NPNP-completeness proofs for the problems at hand. We start with the argument showing containment in NPNP. We observe that given a PQFPQF-tree T with a mapping φ from a candidate set C to the leaves of T, we can verify in polynomial time if a given vote belongs to the domain (T,φ)D(T, ). Proposition B.1. There is a polynomial-time algorithm that given a vote v and a domain (T,φ)D(T, ), defined via a PQFPQF-tree T and a mapping φ , decides whether v belongs to (T,φ)D(T, ). Proof. Let T1,…,TkT_1,…,T_k be the subtrees rooted at the children of the root of T. Given T and φ , we can compute in polynomial time the sets C1,…,CkC_1,…,C_k such that, for each i∈[k]i∈[k], the set CiC_i consists exactly of those candidates that are mapped to leaves of TiT_i. If vote v belongs to (T,φ)D(T, ), every set CiC_i must occupy a contiguous block of vote v. Hence, we first check that each CiC_i is contiguous in v; if some CiC_i is not, then v∉(T,φ)v (T, ). The contiguous blocks then appear in v in a unique order, which we accept if and only if it is permitted by the type of the root: any order for type PP, the left-to-right order or its reversal for type QQ, and exactly the left-to-right order for type FF. Upon acceptance, for each i∈[k]i∈[k] we proceed recursively on the subtree TiT_i with the restricted vote v↾Civ_ _C_i and the restricted mapping φ↾Ci _ _C_i. Vote v belongs to (T,φ)D(T, ) if and only if all these checks succeed. Each node of T is processed once, with polynomial work per node, and T has (m)O (m ) nodes; hence, the verification runs in polynomial time. ∎ This immediately implies that Nearly X Election is in NPNP for all our tree-defined domains. The same holds easily for the Single-PeakedSingle- and Single-CrossingSingle- domains; hence, in the following proofs we omit NPNP-membership arguments. Proposition B.2. Nearly X Election is in NPNP for any ∈GS,GS/bal,GS/cat,Identity,Antagonism,k-Stratification,SeparationX∈\GS, / , / , , , k- , \. Proof. Let E=(C,V)E=(C,V) be the input election of the considered problem. The certificate is a tree T, a mapping φ , and an election E′=(C,V′)E =(C,V ), with the same number of voters as the input election E. All of those objects are of size poly(m,n) (m,n). We check that T has the form required by X by inspecting its shape and node types in (m)O (m ) time; if so, then (T,φ)∈D(T, ) by definition. By Proposition B.1, we verify that each vote v′v in V′V satisfies v′∈(T,φ)v (T, ), and finally that ∑i∈[n]dist(vi,vi′)≤d _i∈[n]dist(v_i,v_i )≤ d where V=(v1,…,vn)V=(v_1,…,v_n) and V′=(v1′,…,vn′)V =(v _1,…,v _n). ∎ B.1 Proof of Theorem 3.1 See 3.1 To prove Theorem 3.1, we use the fact that the GS/catGS/ domain is hereditary, i.e., caterpillar-consistency is closed under candidate deletion (Kraiczy and Elkind 2022). We also use the following auxiliary claim. Lemma B.3. Let ≻1,≻2 _1, _2 be votes over C whose two bottom positions are occupied by the same pair x,y\x,y\ in opposite orders. Then (≻1,≻2)( _1, _2) is caterpillar-consistent if and only if ≻1 _1 and ≻2 _2 agree in every position except the last two. Proof. For the forward direction, suppose that (≻1,≻2)( _1, _2) is caterpillar-consistent w.r.t. a mapping φ=(φ1,…,φm) =( _1,…, _m). We show by induction on |C||C| that ≻1 _1 and ≻2 _2 agree in every position but the last two. For |C|=2|C|=2 there is nothing to prove, so let |C|>2|C|>2. By the recursive characterization, φ1 _1 is first or last in both votes. As both x and y are second-to-last in exactly one of the votes ≻1 _1 and ≻2 _2, neither is at an extreme in both votes, so φ1∉x,y _1∉\x,y\. Since the last position of each vote is occupied by x or y, the candidate φ1 _1 is not last in either, hence is first in both. Deleting φ1 _1 from the top of both votes leaves two votes that still have x,yx,y in their bottom two positions in opposite orders; by the induction hypothesis they agree in every position but their last two. Together with the shared first candidate φ1 _1, the votes ≻1 _1 and ≻2 _2 agree in every position but the last two. For the converse, let (p1,…,pm−2)(p_1,…,p_m-2) be the common prefix of ≻1 _1 and ≻2 _2, and set φ=(p1,…,pm−2,x,y) =(p_1,…,p_m-2,x,y). After deleting p1,…,pi−1p_1,…,p_i-1, the candidate pip_i is first in both remaining votes, so the recursive condition holds for the first m−2m-2 steps. The remaining votes are then (x,y)(x,y) and (y,x)(y,x), both caterpillar with respect to (x,y)(x,y). Hence, both votes lie in (Tcat,φ)D(T^cat, ), so (≻1,≻2)( _1, _2) is caterpillar-consistent. ∎ Now, we present an NPNP-hardness reduction from Kemeny Aggregation. Given a Kemeny Aggregation instance with candidates C=c1,…,cmC=\c_1,…,c_m\, voters V=(v1,…,vn)V=(v_1,…,v_n), and budget d, we construct an election E′=(C′,V′)E =(C ,V ) with C′=C∪f1,…,fd+1∪g1,…,gd+2.C =C∪\f_1,…,f_d+1\∪\g_1,…,g_d+2\. Next, we define the votes V′V as follows. • voter v1′v_1 with vote v1′=(v1,f1,…,fd+1,g1,…,gd+2);v _1=(v_1,f_1,…,f_d+1,g_1,…,g_d+2); • voter vi′v_i for i∈2,…,ni∈\2,…,n\, with vote vi′=(vi,f1,…,fd+1,gd+2,…,g1).v _i=(v_i,f_1,…,f_d+1,g_d+2,…,g_1). We claim dist(E′,GS/cat)≤ddist(E ,GS/ )≤ d if and only if the Kemeny Aggregation instance is a yes-instance. Direction “⇒ ”. Suppose dist(E′,GS/cat)≤ddist(E ,GS/ )≤ d. Then there exists a caterpillar-consistent election E′=(C′,V′)E =(C ,V ) whose votes V′=(v1′,…,vn′)V =(v_1 ,…,v_n ) are obtained from V′V by at most d swaps in total. Because at most d swaps were used, we know that 1. c≻vi′g1c _v_i g_1 and c≻vi′gd+2c _v_i g_d+2 for each i∈[n]i∈[n] and c∈Cc∈ C; 2. gd+2≻vi′g1g_d+2 _v_i g_1 for each i∈[2,n]i∈[2,n]; 3. g1≻v1′gd+2g_1 _v_1 g_d+2. Indeed, violating (1) would require moving g1g_1 or gd+2g_d+2 across the block f1,…,fd+1f_1,…,f_d+1, and violating (2) or (3) would require reversing two candidates with d candidates between them; each needs more than d swaps. Since GS/catGS/ is hereditary, restricting E′E to C′=C∪g1,gd+2C =C∪\g_1,g_d+2\ leaves a caterpillar-consistent election. By properties (1)–(3) above, in every vote of V′↾C′V _ _C the candidates g1g_1 and gd+2g_d+2 occupy the bottom two positions, ordered g1,gd+2g_1,g_d+2 in v1′v_1 and gd+2,g1g_d+2,g_1 in every other vote. Applying Lemma B.3 to v1′v_1 and each vi′v_i with i≥2i≥ 2, all votes of V′↾C′V _ _C agree on their top m positions, which are exactly the candidates of C; let v∗v^* be this common order over C. Since restricting the candidate set C does not increase swap distance, and votes vi′v_i and vi′v_i restricted to C yield votes viv_i and v∗v^*, respectively, we get ∑i=1ndist(vi,v∗)≤∑i=1ndist(vi′,vi′)≤d, _i=1^ndist(v_i,v^*)\;≤\; _i=1^ndist(v_i ,v_i )\;≤\;d, so the Kemeny Aggregation instance is a yes-instance. Direction “⇐ ”. Let v∗=(q1,…,qm)v^*=(q_1,…,q_m) be an ordering over C with ∑idist(vi,v∗)≤d _idist(v_i,v^*)≤ d. Take φ=(q1,…,qm,f1,…,fd+1,g1,…,gd+2). =(q_1,…,q_m,f_1,…,f_d+1,g_1,…,g_d+2). Using a total of at most d swaps among the candidates of C in all votes of V′V , we bring them into the order v∗v^* while leaving all other candidates in place. The resulting votes have one of two forms: (q1,…,qm,f1,…,fd+1,g1,…,gd+2);(q_1,…,q_m,f_1,…,f_d+1,g_1,…,g_d+2); (q1,…,qm,f1,…,fd+1,gd+2,…,g1).(q_1,…,q_m,f_1,…,f_d+1,g_d+2,…,g_1). The first type of vote ranks the candidates exactly in as φ , so it lies in (Tcat,φ)D(T^cat, ). For the second form, its prefix through fd+1f_d+1 coincides with that of φ , so the recursive characterization removes q1,…,qm,f1,…,fd+1q_1,…,q_m,f_1,…,f_d+1 from the top; the remaining vote (gd+2,…,g1)(g_d+2,…,g_1) and remaining mapping (g1,…,gd+2)(g_1,…,g_d+2) are then matched by removing g1,…,gd+2g_1,…,g_d+2 from the bottom. Hence the second type of vote also lies in (Tcat,φ)D(T^cat, ), and dist(E′,GS/cat)≤ddist(E ,GS/ )≤ d. Since Kemeny Aggregation is already NPNP-hard for four voters (Dwork et al. 2001) and the reduction preserves the number of voters, the hardness holds for n=4n=4. B.2 Proof of Theorem 3.2 See 3.2 Proof. Before presenting our reduction, we introduce some notation. For an integer k∈ℕk that is a power of 22, let TkT_k denote the binary, balanced QQ-tree with k leaves. For a given tree TkT_k and a list C→ C of candidates, we let (C→)( C) denote the bijection from C to the leaves of TkT_k for which the left-to-right traversing of the leaves yields the ordering C→ C of the candidates. Let Ek=(Ck,Vk)E_k=(C_k,V_k) be an election with Ck=c1,…,ckC_k=\c_1,…,c_k\ and Vk=(v1,…,vk)V_k=(v_1,…,v_k) where vote viv_i is obtained from the ordering c1,…,ckc_1,…,c_k of candidates by moving cic_i to the top position, i.e., vi=(ci,c1,…,ci−1,ci+1,…,ck)v_i=(c_i,c_1,…,c_i-1,c_i+1,…,c_k). We use the following property of such elections. Claim B.4. Let k be a power of 2, and define the function g(k)=k(k/2−1)g(k)=k( k2-1). Then (Ek,d)(E_k,d) is a yes-instance of Nearly GS/balGS/ Election if and only if d≥g(k)d≥ g(k). Moreover, EkE_k has swap distance g(k)g(k) from an election in (Tk,(c1,…,ck))D(T_k,(c_1,…,c_k)). Proof. We use induction on logk k. The claim is easily seen to hold for k=2k=2 with g(2)=0g(2)=0, and it is also straightforward to check that for k=4k=4 we obtain g(4)=4g(4)=4.22 2 In fact, for any mapping φ from ci:i∈[4]\c_i:i∈[4]\ to the leaves of the balanced binary tree T4T_4, the minimal swap distance of E4E_4 from some election in (T4,φ)D(T_4, ) is exactly 44. Assume that it holds for k/2 k2. Suppose now that there is a GS-balanced election (Ck,Vk′)(C_k,V _k) with Vk′=(v1′,…,vk′)V _k=(v _1,…,v _k) and a mapping φ from CkC_k to the leaves of TkT_k such that each vi′v _i is in (Tk,φ)D(T_k, ). Let us define s⋆=∑i∈[k]swap(vi,vi′)s = _i∈[k]swap(v_i,v _i). We aim to show s⋆≥g(k)s ≥ g(k). Let T1T^1 and T2T^2 be the two subtrees rooted at the two children of the root of T. Let SiS_i be the set of candidates mapped by φ to leaves in TiT^i for i∈[2]i∈[2]. Observe that we can obtain Vk′V _k with at most s⋆s swaps by first performing only those swaps that are between candidates of S1S_1 and S2S_2, obtaining some election (Ck,Vk′)(C_k,V _k), and only then performing the swaps between candidates belonging to the same set S1S_1 or S2S_2. Note that the ordering of the candidates in SiS_i for some i∈[2]i∈[2] as appearing in the votes of Vk′V _k is as follows: in k/2 k2 votes from Vk′V _k, they appear in their “default” order (in increasing order of their subscripts), and the remaining k/2 k2 votes in Vk′V _k can be obtained by taking each candidate c in SiS_i and moving it to the top of this default ordering of SiS_i. Hence, these k/2 k2 votes form an election that is isomorphic to Ek/2E_ k2. By our induction hypothesis, this shows that the minimum number of swaps necessary to reach Vk′V _k from Vk′V _k is at least twice the swap distance of Ek/2E_ k2 from a GS-balanced election, i.e., 2g(k/2)2g( k2). We will now show that the swap distance of V from V′V is at least k2/4 k^24. Let V′=(v1′,…,vk′)V =(v _1,…,v _k) where vi′v _i is the vote in V′V with minimum swap distance to viv_i, for each i∈[k]i∈[k]. Consider any two votes vav_a and vbv_b such that ca∈S1c_a∈ S_1 and cb∈S2c_b∈ S_2. We will show that swap(va,va′)+swap(vb,vb′)≥k/2swap(v_a,v _a)+swap(v_b,v _b)≥ k2. First, suppose that all candidates in S1S_1 precede all candidates in S2S_2 in both va′v _a and vb′v _b. In this case, candidate cbc_b, ranked at the first position in vbv_b, needs to be swapped with all candidates in S1S_1 to reach its position in vb′v _b, which means k/2 k2 swaps. Similarly, if all candidates in S2S_2 precede all candidates in S1S_1 in both va′v _a and vb′v _b, then cac_a needs k/2 k2 swaps in vav_a to reach its position in va′v _a. Assume now that candidates in S1S_1 precede those in S2S_2 in exactly one of va′v _a and vb′v _b. Then every pair of candidates from (S1∖ca)×(S2∖cb)(S_1 \c_a\)×(S_2 \c_b\) needs to be swapped either when turning vav_a into va′v _a, or when turning vbv_b into vb′v _b. This yields swap(va,va′)+swap(vb,vb′)≥(k/2−1)2>k/2swap(v_a,v _a)+swap(v_b,v _b)≥( k2-1)^2> k2 which holds for each k≥8k≥ 8. Pairing up the votes in V so that for each pair, the candidates on the top positions are in different sets S1S_1 or S2S_2, we obtain that ∑iswap(vi,vi′)≥(k/2)2 _iswap(v_i,v _i)≥( k2)^2, as promised. It follows that s⋆≥2g(k/2)+k2/4=k2/4−k+k2/4=k(k/2−1)s ≥ 2g( k2)+ k^24= k^24-k+ k^24=k( k2-1), proving the first direction of the claim. It remains to observe that we can obtain a GS-balanced election Ek′∈(Tk,(c1,…,ck))E _k (T_k,(c_1,…,c_k)) from EkE_k as follows. First, we move all candidates in c1,…,ck/2\c_1,…,c_ k2\ to the first k/2 k2 positions in each vote; this requires 00 swaps in each vote viv_i, i∈[k/2]i∈[ k2], and exactly k/2 k2 swaps in all remaining votes. Hence, this yields k2/4 k^24 swaps. Note that the subelection restricted to Ck/2=c1,…,ck/2C_ k2=\c_1,…,c_ k2\ contains the vote (c1,…,ck/2)(c_1,…,c_ k2) exactly k/2 k2 times, and additionally, a copy of Ek/2E_ k2. Thus, we can turn this subelection into a GS-balanced election using g(k/2)g( k2) swaps. Dealing with the subelection restricted to Ck∖Ck/2C_k C_ k2 in the same way, we obtain that the swap distance of EkE_k from Ek′E _k is exactly 2g(k/2)+k2/4=g(k)2g( k2)+ k^24=g(k). This finishes our proof. ∎ The Input. We now present a reduction from a variant of the Balanced Maximum Vertex Coverage (BMVC) problem on bipartite graphs. The input of this problem is a bipartite graph G=(U,W,F)G=(U,W;F) with two integers k and t, and the question is whether G contains k vertices from U and k vertices from W such that together they cover at least t edges. Claim B.5. BMVC is NPNP-complete even if k is a power of 22, and |U|=|W|=n+k|U|=|W|=n+k for some integer n>2kn>2k that is a power of 22. Proof. Containment in NPNP is trivial. We give a reduction from the Constraint Bipartite Vertex Cover (CBVC) problem which, given a bipartite graph H with partite sets A and B together with two integers kAk_A and kBk_B, asks whether H contains a vertex cover of the form A′∪B′A ∪ B such that A′⊆A A has size at most kAk_A and B′⊆B B has size at most kBk_B. This problem is NPNP-complete (Kuo and Fuchs 1987). Let k be power of 22 at least maxkA,kB \k_A,k_B\. We create a graph H′H as follows: we first add (k−kA)(k-k_A) new vertices to A and (k−kB)(k-k_B) new vertices to B, and then for each of the newly added 2k−kA−kB2k-k_A-k_B vertices, we create 2k+12k+1 neighbors on the other side, each of them having degree 1. Notice that the newly added vertices must be contained in every vertex cover of H′H of size at most 2k2k. Thus, (H,kA,kB)(H,k_A,k_B) is a yes-instance of CBVC if and only if there are k vertices on each side of H′H such that together they cover all edges of H′H , or in other words, if (H′,k,mH′)(H ,k,m_H ) is a yes-instance of Balanced Maximum Vertex Coverage where mH′m_H is the number of edges in H′H . This shows the NPNP-hardness of the BMVC problem with the desired requirement on k. As for the requirement on |U||U| and |W||W|, we can pick any integer n>2kn>2k that is a power of 22, and then ensure the condition |U|=|W|=n+k|U|=|W|=n+k by adding the necessary number of isolated vertices to the input graph. ∎ The Construction. Given our input graph G=(U,W,F)G=(U,W;F) with |U|=|W|=n+k|U|=|W|=n+k and integers k and t for BMVC with the properties as in Claim B.5, we construct an election (C,V)(C,V) as follows. Let α=6|U|4α=6|U|^4. The set of candidates consists of the vertices in U∪WU∪ W as well as two sets B1B_1 and B2B_2 of dummies with |B1|=2n−k|B_1|=2n-k and |B2|=4n−k|B_2|=4n-k. We create two sets of anchor voters, A and A′A with |A|=|A′|=α|A|=|A |=α. Their preferences are as follows: a a :B1→,U→,W→,B2→ : B_1, U, W, B_2 ∀a∈A; ∀ a∈ A; a′ a :B1→,U←,W←,B2→ : B_1, U, W, B_2 ∀a′∈A′. ∀ a ∈ A . We further create incidence voters vu,wv_u,w and vu,w′v _u,w for each u∈Uu∈ U and w∈Ww∈ W; their preferences are as below: vu,w v_u,w :B1→,W∖w→,u,w,U∖u→,B2→ : B_1, W \w\,u,w, U \u\, B_2 if u,w∈F; if $\u,w\∈ F$; vu,w v_u,w :B1→,W∖w→,w,u,U∖u→,B2→ : B_1, W \w\,w,u, U \u\, B_2 if u,w∉F; if $\u,w\∉ F$; vu,w′ v _u,w :B1→,w,W∖w←,U∖u←,u,B2→. : B_1,w, W \w\, U \u\,u, B_2. We finish the construction by setting our budget as d=α⋅2nk d=α· 2nk +2k(3n+k)(n+k)2 +2k(3n+k)(n+k)^2 +4(n+k)(g(n)+g(k))+|F|−2t. +4(n+k)(g(n)+g(k))+|F|-2t. We are going to show that (G,k,t)(G,k,t) is a yes-instance of Balanced Maximum Vertex Coverage if and only if the constructed instance ((C,V),d)((C,V),d) of Nearly GS/balGS/ Election is a yes-instance. Direction “⇒ ”. First assume that vertex sets U⋆⊆U U and W⋆⊆W W form a solution to our instance of Balanced Maximum Vertex Coverage. Let T8nT_8n be the balanced binary tree with 8n8n leaves, and consider the mapping φ⋆=(B1→,U⋆→,U∖U⋆→,W∖W⋆→,W⋆→,B2→) =( B_1, U , U U , W W , W , B_2). To turn the constructed election (C,V)(C,V) into an election in (T8n,φ⋆)D(T_8n, ), we perform the following swaps: First, we move all candidates in U⋆U to the k positions right after the last dummy in B1B_1 and all candidates in W⋆W to the k positions right before the first dummy in B2B_2 in all votes. In a pair of anchor votes from A×A′A× A , this step requires exactly 2k⋅n2k· n swaps in total. In a pair vu,wv_u,w, vu,w′v _u,w of incidence voters, we need to swap • all pairs in (U×W)∖((U∖U⋆)×(W∖W⋆))(U× W) ((U U )×(W W ) ) in both votes, except for (u,w)(u,w) in vu,wv_u,w if u,w∈F\u,w\∈ F; • all pairs in ((U∖U⋆)×U⋆)∪((W∖W⋆)×W⋆)((U U )× U )∪((W W )× W ) exactly once in total in the two votes. This requires 2(3n+k)k2(3n+k)k swaps in these two votes, unless (i) u∈U⋆u∈ U or w∈W⋆w∈ W , and (i) u,w∈F\u,w\∈ F, in which case we need one swap less. Let F⋆F denote the set of edges in G incident to some vertex in U⋆∪W⋆U ∪ W . Then in this step, we perform 2k(3n+k)(n+k)2−|F⋆|2k(3n+k)(n+k)^2-|F | swaps in all incidence votes. Taking into account the swaps in anchor votes, we obtain a total of α⋅2kn+2k(3n+k)(n+k)2−|F⋆|α· 2kn+2k(3n+k)(n+k)^2-|F | (1) swaps in this step. Second, we also swap u with w in each incidence vote vu,wv_u,w where u∈U∖U⋆u∈ U U , w∈W∖W⋆w∈ W W , and u,w∈F\u,w\∈ F. This means |F∖F⋆||F F | (2) swaps. Let E′E denote the election obtained at this point. Notice that for each anchor voter a in E′E we know B1≻aU⋆≻aU∖U⋆≻aW∖W⋆≻aW⋆≻aB2,B_1 _aU _aU U _aW W _aW _aB_2, whereas for each incidence voter v we know B1≻vU⋆≻vW∖W⋆≻vU∖U⋆≻vW⋆≻vB2.B_1 _vU _vW W _vU U _vW _vB_2. Recall also that each of the sizes |U⋆|=|W⋆||U |=|W |, |B1∪U⋆||B_1∪ U |, |U∖U⋆|=|W∖W⋆||U U |=|W W |, and |B2∪W⋆||B_2∪ W | are powers of 22. B1B_1U⋆U U U⋆U to3.6pt to6.6pt 0.3pt -0.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @setlinewidth @begingroup@stroke-width=0.6pt @inpgf@ignorespaces @roundcap @begingroup@stroke-linecap=round @inpgf@ignorespaces @stroke @drawpath@unclippedM 4.15 0 L 0 8.3fill:none @inpgf@ignorespaces @closescope @closescope @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope U W W⋆W to3.6pt to6.6pt 0.3pt -0.3pt to0.0pt @begingroup@_scopebegin=1 @begingroup@stroke=#000000 @begingroup@fill=#000000 @setlinewidth @begingroup@stroke-width=0.4pt @inpgf@ignorespaces to0.0pt @begingroup@_scopebegin=1 @inpgf@ignorespaces @inpgf@ignorespaces @begingroup@_scopebegin=1 @setlinewidth @begingroup@stroke-width=0.6pt @inpgf@ignorespaces @roundcap @begingroup@stroke-linecap=round @inpgf@ignorespaces @stroke @drawpath@unclippedM 4.15 0 L 0 8.3fill:none @inpgf@ignorespaces @closescope @closescope @inpgf@ignorespaces @inpgf@ignorespaces @inpgf@ignorespaces @discardpath @closescope @closescope W W⋆W B2B_22n−k2n-kkknnnnkk4n−k4n-kt1t_1t2t_2t11t_11t12t_12t121t_121t122t_122 Figure 3: Illustration for the proof of Theorem 3.2. The figure depicts the prefect binary tree T8nT_8n. The candidate set displayed in the rectangle at the bottom of a given subtree contains those candidates that are mapped by φ⋆ to the leaves of the given subtree, with the size of this set written underneath. Third, let us now perform all swaps necessary to turn election E′E into an election in the domain (T8n,φ⋆)D(T_8n, ). Let us now calculate the swaps necessary for this. Swaps involving candidates in U⋆U . Notice that E′E restricted to candidates in U⋆U contains • |W||W| copies of an election EU⋆′E _U that is isomorphic to EkE_k with the default ordering of the candidates being U⋆→ U , • |W||W| copies of the reverse of EU⋆′E _U (obtained from EU⋆′E _U by reversing all votes), and • additional votes of the form U⋆→ U or U⋆← U . By Claim B.4, we know that we need g(k)g(k) swaps to turn one copy of EU⋆′E _U into a GS-balanced election in (Tk,(U⋆→))D(T_k,( U )). Since reversing all votes does not change the distance of an election from the GS-balanced domain, and moreover, (Tk,(U⋆→))=(Tk,(U⋆←))D(T_k,( U ))=D(T_k,( U )), we get that the distance of the restriction of E′E to U⋆U from the GS-balanced domain is exactly 2(n+k)⋅g(k)2(n+k)· g(k). Swaps involving candidates in U∖U⋆U U . Using the same arguments as in the previous case, we get that the restriction of E′E to candidates in U∖U⋆U U has swap distance 2(n+k)⋅g(n)2(n+k)· g(n) from (Tn,(U∖U⋆→))D(T_n,( U U )). Swaps involving candidates of W. By symmetry, the total number of swaps necessary to turn the restriction of E′E to candidates in W⋆W , as well the restriction of E′E to candidates in W∖W⋆W W into a GS-balanced election in (Tk,(W⋆→))D(T_k,( W )) and (Tn,(W∖W⋆→))D(T_n,( W W )), respectively, is 2(n+k)(g(k)+g(n))2(n+k)(g(k)+g(n)). These swaps are sufficient, because they turn the election into one in (T8n,φ⋆)D(T_8n, ). Indeed, notice that T8nT_8n contains a QQ-node whose two children are the roots of the subtrees, each of size n, that contain exactly those leaves to which candidates in U∖U⋆U U and in W∖W⋆W W , respectively, are mapped—enabling the reversed ordering of these two subtrees; see Figure 3 for an illustration. Altogether, the total number of swaps performed in this step is 4(n+k)(g(k)+g(n)).4(n+k)(g(k)+g(n)). (3) Summing up (1)–(3), we obtain that the total number of swaps performed is d+2t−2|F⋆|d+2t-2|F |. Since U⋆∪W⋆U ∪ W is a solution to our input instance, the set F⋆F of edges covered by the vertices in U⋆∪W⋆U ∪ W must satisfy |F⋆|≥t|F |≥ t. Thus, we get that the swap-distance of (C,V)(C,V) from the GS-balanced domain is at most d+2t−2|F⋆|≤d+2t-2|F |≤ d, which proves the first direction of our claim. Direction “⇐ ”. Suppose now that (C,V)(C,V) has swap distance at most d from some GS-balanced election (C,V′)(C,V ). For each vote v in V, let π(v)π(v) denote the corresponding vote in V′V that belongs to the domain (T8n,φ)D(T_8n, ) for some φ . Since all votes in A are the same, we can assume that π(a)π(a) is the same vote for each a∈Aa∈ A; the analogous claim holds for votes in A′A . Consider now an anchor vote a∈Aa∈ A, and let Ca1C_a^1 and Ca2C_a^2 denote the candidates in the first 2n2n and the last 4n4n positions in π(a)π(a). Consider now a pair of anchor votes (a,a′)∈A×A′(a,a )∈ A× A . By the definition of the allowed permutations in a QQ-tree, we know that either (i) Cai=Ca′iC_a^i=C_a ^i or (i) Cai∩Ca′i=∅C_a^i∩ C_a ^i= for both i∈[2]i∈[2]. We claim that only the former case can happen, for both i∈[2]i∈[2]. To see this, notice that in case (i), each dummy b∈Bib∈ B_i has to be moved away from the outermost |Bi|+k|B_i|+k positions (i.e., the first 2n2n positions for i=1i=1 and the last 4n4n positions for i=2i=2) either in a or in a′a , which yields 2n⋅|Bi|>2n2n·|B_i|>2n swaps in total for (a,a′)(a,a ). Hence, this would yield at least α⋅2n⋅(2n−k)≥α⋅(2nk+n)>dα· 2n·(2n-k)≥α·(2nk+n)>d where the last inequality holds due to our choice of α. Thus, we have that (i) holds for both i∈[2]i∈[2]. Then candidates in Si=Cai∖BiS_i=C_a^i B_i need to be moved into the outermost |Bi|+k|B_i|+k positions; by the ordering of candidates in a and in a′a , the number of swaps necessary for this can be calculated as follows: • Moving a candidate u∈U∩S1u∈ U∩ S_1 to within the first 2n2n positions requires n swaps within a pair of votes in (a,a′)∈A×A′(a,a )∈ A× A , since u needs to be swapped with every candidate in U∖S1U S_1 exactly once. • Moving a candidate c in S1∖US_1 U to the first k position following candidates in B1B_1 requires at least 2n2n swaps within a and a′a , because c must be swapped with all candidates in U∪B1∖C1aU∪ B_1 C^a_1 in both votes a and a′a . • Similarly, moving a candidate c to within the last 4n4n position requires n swaps if c∈S2∩Wc∈ S_2∩ W and 2n2n swaps if c∈S2∖Wc∈ S_2 W. This implies that S1⊆US_1 U with |S1|≤k|S_1|≤ k and S2⊆WS_2 W with |S2|≤k|S_2|≤ k, because otherwise we would have to perform at least α(2nk+n)>dα(2nk+n)>d swaps in the anchor votes. In particular, it follows that there exist subsets U⋆⊆U U and W⋆⊆W W of candidates with |U⋆|=|W⋆|=k|U |=|W |=k such that Ca1=B1∪U⋆C_a^1=B_1∪ U and Ca2=B2∪W⋆C_a^2=B_2∪ W for all anchor votes a∈A∪A′a∈ A∪ A . The number of swaps necessary to move these candidates to their positions in π(a)π(a) in each anchor vote a∈A∪A′a∈ A∪ A is α⋅2nkα· 2nk in total. Let us consider the number of swaps necessary to move these candidates to their positions in the incidence votes. It is easy to see that moving Ca1C_a^1 to the first 2n2n positions in some incidence vote requires fewer swaps than moving them to the second set of 2n2n positions (or even further), because the former requires at most k(2n+k)k(2n+k) swaps, while the latter requires at least |B1|⋅2n=(2n−k)⋅2n>k(2n+k)|B_1|· 2n=(2n-k)· 2n>k(2n+k) swaps; here we used the assumption n>2kn>2k. Hence, in all votes of V′V , the first 2n2n positions are occupied by candidates in B1∪U⋆B_1∪ U . Similarly, in all votes of V′V , the last 4n4n positions are occupied by candidates in B2∪W⋆B_2∪ W . This implies that the mapping φ from C to the leaves of T8nT_8n has the following properties: Let us denote the children of the root by t1t_1 and t2t_2, and let t11t_11 and t12t_12 denote the children of t1t_1. Then the candidates mapped to the leaves in the subtree rooted at t11t_11, t12t_12, and t2t_2, are B1∪U⋆B_1∪ U , (U∖U⋆)∪(W∖W⋆)(U U )∪(W W ), and B2∪W⋆B_2∪ W , respectively. Let us denote the two children of t12t_12 as t121t_121 and t122t_122. See again Figure 3. Let us call the set of swaps required to move the candidates in B1∪U⋆B_1∪ U into the first 2n2n positions and the candidates in B2∪W⋆B_2∪ W into the last 4n4n positions, without swapping any two candidates belonging to the same set B1∪U⋆B_1∪ U or B2∪W⋆B_2∪ W , phase-1 swaps. The number of such swaps is exactly the value in (1) where F⋆F denotes the set of edges incident to at least one vertex in U⋆∪W⋆U ∪ W ; the same arguments presented in the paragraph preceding (1) are valid here as well. After performing all phase-1 swaps, the n positions after candidates in B1∪U⋆B_1∪ U contain the candidates in U∖U⋆U U in all anchor votes. Hence, the candidates mapped by φ to the leaves in the subtree rooted at t121t_121 and at t122t_122 must be those is U∖U⋆U U and in W∖W⋆W W , respectively, since otherwise we would need at least one additional swap in each anchor vote; however adding α to the value in (1) already exceeds the budget d, due to α⋅2nk+α>dα· 2nk+α>d. Thus, in order to obtain π(vu,w)π(v_u,w) from some incidence vote vu,wv_u,w where u∈U∖U⋆u∈ U U , w∈W∖W⋆w∈ W W , and u,w∈F\u,w\∈ F, we also need to swap u and w. Let us call such swaps phase-2 swaps; their number is exactly |F∖F⋆||F F |. After performing all phase-1 and phase-2 swaps, we obtain an election that is isomorphic with the election E′E described in the first direction of this proof; note that this holds irrespective of the choice of U⋆U and W⋆W . We have already proved that turning E′E into a GS-balanced election—specifically, to an election in (T8n,φ⋆)D(T_8n, ) for φ⋆=(B1→,U⋆→,U∖U⋆→,W∖W⋆→,W⋆→,B2→) =( B_1, U , U U , W W , W , B_2) —requires (4(n+k)(g(n)+g(k))4(n+k)(g(n)+g(k))) swaps; see the calculations leading to (3). Hence, the total number of swaps necessary to turn the original election into a GS-balanced election is at least the sum of the values (1)–(3), that is, at least d+2t−2|F⋆|d+2t-2|F |. Recall that we assumed this value not to exceed the budget d, which is only possible if |F⋆|≥t|F |≥ t, i.e., the vertices in U⋆∪W⋆U ∪ W together cover at least t edges in the input graph. This shows the correctness of our reduction. ∎ B.3 Proof of Theorem 3.3 See 3.3 We prove the two statements of the theorem separately. We start with the polynomial-time solvability of Nearly 2-Stratification2- Election. Theorem B.6. Nearly 2-Stratification2- Election is in PP. Proof. Let election E=(C,V)E=(C,V) with V=(v1,…,vn)V=(v_1,…,v_n) and budget d be our input instance, with |C|=m|C|=m. Let T be a PQFPQF-tree whose root is of type FF and has two children, p1p_1 and p2p_2, both of type PP and with m/2m/2 leaves. Our algorithm computes an optimal mapping of the candidates to the leaves of T in a surprisingly simple way: it computes the Borda score of each candidate, and maps the candidate with the i-th highest Borda score to the i-th leaf of T, resolving ties arbitrarily. Let C1C_1 and C2C_2 denote the set of candidates mapped to children of p1p_1 and p2p_2, respectively. We claim that E has swap distance at most d to the 2-Stratification2- domain if and only if it has swap distance at most d from (T,φ)D(T, ). Note that the latter can be checked in polynomial time: we just need to sum up for each vote v the number of candidate pairs (c1,c2)(c_1,c_2) for which c1∈C1c_1∈ C_1 and c2∈C2c_2∈ C_2 but c2≻vc1c_2 _vc_1. Since computing the Borda scores can also be done in polynomial time, we obtain a polynomial-time algorithm. It remains to prove its correctness. Let S1S_1 and S2S_2 be a partitioning of C with |S1|=|S2||S_1|=|S_2| such that the swap distance of E to (T,φS)D(T, _S) is minimal where φS _S maps candidates in SiS_i to the children of pip_i for i∈[2]i∈[2]. Assume for the sake of contradiction that S1≠C1S_1≠ C_1. Then there are candidates a1∈S1a_1∈ S_1 and a2∈S2a_2∈ S_2 such that a2a_2 has higher Borda score than a1a_1, that is, ∑v∈Vposv(a2)<∑v∈Vposv(a1). _v∈ Vpos_v(a_2)< _v∈ Vpos_v(a_1). (4) Create the partitioning S1′S _1 and S2′S _2 by switching a1a_1 and a2a_2, so that S1′=S1∖a1∪a2S _1=S_1 \a_1\∪\a_2\ and S2′=S2∖a2∪a1S _2=S_2 \a_2\∪\a_1\. Let dSd_S and dS′d_S denote the swap distance of E from (T,φS)D(T, _S) and from (T,φS′)D(T, _S ), respectively, where φS′ _S maps candidates in Si′S _i to the children of pip_i, i∈[2]i∈[2]. Note that for each vote in V, the number of swaps between candidates in C∖a1,a2C \a_1,a_2\ is the same in both cases. The number of swaps involving either a1a_1 or a2a_2 in some vote v∈Vv∈ V, denoted by dS(v)d_S^(v) and dS′(v)d_S ^(v) to obtain a vote in (T,φS)D(T, _S) and in (T,φS′)D(T, _S ), respectively, can be computed as follows. If a1≻va2a_1 _va_2, then we get dS(v) d_S^(v)\! =|b:b∈S2,b≻va1|+|b:b∈S1,a2≻vb|, =|\b b∈ S_2,b _va_1\|+|\b b∈ S_1,a_2 _vb\|, dS′(v) d_S ^(v)\! =|b:b∈S1,a1≻vb|+|b:b∈S2,b≻va2|+1 =|\b b∈ S_1,a_1 _vb\|+|\b b∈ S_2,b _va_2\|+1 where the last term corresponds to swapping a1a_1 and a2a_2. Thus, we get dS′(v)−dS(v) d_S ^(v)-d_S^(v) =|b:b∈S1,a1≻vb≻va2| =|\b b∈ S_1,a_1 _vb _va_2\| +|b:b∈S2,a1≻vb≻va2|+1 +|\b b∈ S_2,a_1 _vb _va_2\|+1 =posv(a2)−posv(a1). =pos_v(a_2)-pos_v(a_1). By symmetry, for the case a2≻va1a_2 _va_1 we get dS(v)−dS′(v)=posv(a1)−posv(a2)d_S^(v)-d_S ^(v)=pos_v(a_1)-pos_v(a_2). Summing up over all votes, we get dS′−dS=∑v∈VdS′(v)−dS(v)=∑v∈Vposv(a2)−posv(a1)<0d_S -d_S=\! _v∈ Vd_S ^(v)-d_S^(v)=\! _v∈ Vpos_v(a_2)-pos_v(a_1)\!<\!0 where the last inequality follows from Equation 4. Thus, we get dS′<dSd_S <d_S which contradicts to our choice of (S1,S2)(S_1,S_2). This proves that S1=C1S_1=C_1, i.e., our algorithm correctly finds an optimal partitioning of C. ∎ Next, we show that Nearly SeparationSeparation Election can be solved in FPT time when parameterized by the number of voters. We present a simple approach that relies on our polynomial-time algorithm for Nearly 2-Stratification2- Election. Proposition B.7. The Nearly SeparationSeparation Election problem can be solved in ∗(2n)O^*(2^n) time. Proof. By the definition of the SeparationSeparation domain, we know that an election (C,V)(C,V) is in a SeparationSeparation domain if and only if we can reverse a set V′V of votes in E such that the obtained election is in a 2-Stratification2- domain. Hence, it suffices to guess this set V′V of voters and run the polynomial-time algorithm in Theorem B.6 for Nearly 2-Stratification2- Election. Since there are 2n2^n possibilities to choose V′V , we obtain the claimed running time. ∎ B.4 Proof of Theorem 3.4 See 3.4 We prove the two results separately. We start with the NPNP-completeness of Nearly 3-Stratification3- Election. Theorem B.8. Nearly 3-Stratification3- Election is NPNP-complete. Proof. We reduce from the Clique problem. Let (G,k)(G,k) be our instance for Clique with input graph G=(U,F)G=(U,F); we may assume that k≥2k≥ 2, |U|>k|U|>k, and |F|≥(k2)|F|≥ k2, since otherwise the instance can be solved trivially. Let us construct an election (C,V)(C,V) as follows. We define integers α and β as α α =4|F|(|F|+|U|−k−(k2)), =4|F| (|F|+|U|-k- k2 ), β β =2(k(|U|−k)+(k2)(|F|−(k2))). =2 (k(|U|-k)+ k2 (|F|- k2 ) ). First, for each vertex in U and each edge in F, we create a candidate with the same name. Next, we create 2β2β dummy candidates d1,…,d2βd_1,…,d_2β, as well as additional sets B1B_1 and B2B_2 of dummies whose sizes satisfy γ=|B1|+|U|−k=k+(k2)+2β=|B2|+|F|−(k2)γ=|B_1|+|U|-k=k+ k2+2β=|B_2|+|F|- k2 for some integer γ. This finishes the definition of our candidate set, with 3γ3γ candidates. We create two sets of anchor voters, A and A′A with |A|=|A′|=α|A|=|A |=α. Their preferences, provided as a list, are as follows: a a :B1,U→,d1,…,d2β,F→,B2∀a∈A; :B_1, U,d_1,…,d_2β, F,B_2 ∀ a∈ A; a′ a :B1,U←,d2β,…,d1,F←,B2∀a′∈A′. :B_1, U,d_2β,…,d_1, F,B_2 ∀ a ∈ A . We further create incidence voters wf,uw_f,u and wf,u′w _f,u for each edge f∈Ff∈ F and each endpoint u∈fu∈ f; their preferences are as below. wf,u w_f,u :B1,d1,…,dβ,u,U∖u→,F∖f→,f, :B_1,d_1,…,d_β,u, U \u\, F \f\,f, dβ+1,…,d2β,B2; d_β+1,…,d_2β,B_2; wf,u′ w _f,u :B1,d1,…,dβ,U∖u←,f,u,F∖f←, :B_1,d_1,…,d_β, U \u\,f,u, F \f\, dβ+1,…,d2β,B2. d_β+1,…,d_2β,B_2. Hence, we have 2α+4|F|2α+4|F| voters in total. We finish the construction by setting our budget as d=32α⋅β+|F|⋅β+2|F|−2(k2).d= 32α·β+|F|·β+2|F|-2 k2. First, assume that G contains a clique of size k whose vertex and edge set are UKU_K and FKF_K, respectively. We are going to modify the votes in our election as follows. In each vote, we upshift U∖UKU U_K, meaning that we move all candidates in U∖UKU U_K to the |U|−k|U|-k positions right after B1B_1, and we downshift F∖FKF F_K, meaning that we move all candidates in F∖FKF F_K to the |F|−(k2)|F|- k2 positions right before B2B_2. The number of swaps necessary for this can be calculated as follows: • Consider a pair of anchor votes a∈Aa∈ A and a′∈A′a ∈ A . Since the vertex candidates appear in reverse order in a and a′a , for each candidate x∈U∖UKx∈ U U_K and each y∈UKy∈ U_K exactly one of these two votes ranks y above x; hence, upshifting U∖UKU U_K costs exactly k(|U|−k)k(|U|-k) swaps in the pair a,a′\a,a \, and thus α⋅k(|U|−k)α· k(|U|-k) swaps in total for all anchor votes. Note that no swaps between vertex candidates and dummies or edge candidates are necessary in anchor votes. • By the same arguments, downshifting F∖FKF F_K in all anchor votes requires α⋅(k2)(|F|−(k2))α· k2(|F|- k2) swaps in total. • In the incidence vote pair wf,uw_f,u and wf,u′w _f,u for some f and u, upshifting U∖UKU U_K requires each candidate in U∖UKU U_K to be swapped with the β dummies d1,…,dβd_1,…,d_β in both of these votes, and—using again that the vertex candidates appear in reverse order in wf,uw_f,u and wf,u′w _f,u—with each candidate of UKU_K exactly once, yielding (|U|−k)(k+2β)(|U|-k)(k+2β) swaps in the pair, not counting the possible swap between f and u in the vote wf,u′w _f,u. • Similarly, downshifting F∖FKF F_K in each pair of incidence votes requires (|F|−(k2))((k2)+2β)(|F|- k2)( k2+2β) swaps, again not counting the possible swap between f and u in the vote wf,u′w _f,u. • Finally, notice that we do not need to swap f and u in wf,u′w _f,u if and only if u∈UKu∈ U_K and f∈FKf∈ F_K both hold. Hence, we need α⋅β/2α· β2 swaps in total in the anchor votes, and 2|F|⋅(β/2+2β(|U|−k+|F|−(k2)))+s⋆==|F|⋅β+α⋅β+s⋆2|F|· ( β2+2β (|U|-k+|F|- k2 ) )+s =\\ =|F|·β+α·β+s swaps in incidence votes where s⋆s denotes the number of swaps between vertex and edge candidates in all incidence votes. Since K is a clique, we know that s⋆=2|F|−2(k2)s =2|F|-2 k2. Therefore, the total number of swaps is 32α⋅β+|F|⋅β+2|F|−2(k2)=d. 32α·β+|F|·β+2|F|-2 k2=d. Observe that all of the obtained votes contain B1∪U∖UKB_1∪ U U_K on the first γ positions, and contain B2∪F∖FKB_2∪ F F_K on the last γ positions. Thus, all of these votes belong to the 3-Stratification3- domain determined by the tree whose first P-node has its leaves labeled with B1∪U∖UKB_1∪ U U_K, whose third P-node has its leaves labeled with B2∪F∖FKB_2∪ F F_K, leaving the dummies d1,…,d2βd_1,…,d_2β and the candidates in UK∪FKU_K∪ F_K for the second P-node. Hence, the constructed election with budget d is a yes-instance of Nearly 3-Stratification3- Election. For the other direction, assume that by applying at most d swaps, we can obtain an election (C,V′)(C,V ) that belongs to the 3-Stratification3- domain, i.e., we can partition the candidates set into sets C1,C2,C3C_1,C_2,C_3, each of size γ, such that in each vote, the first γ candidates are from C1C_1 and the last γ candidates are from C3C_3. Note first that we may assume that B1⊆C1B_1 C_1 and B2⊆C3B_2 C_3: indeed, each candidate of B1B_1 is ranked above every candidate of C∖B1C B_1 in each vote, so if some b∈B1b∈ B_1 were contained in C2∪C3C_2∪ C_3 while some candidate c∉B1c∉ B_1 is contained in C1C_1, then exchanging the roles of b and c would not increase the number of necessary swaps in any vote; the argument for B2B_2 is symmetric. We claim that C1⊆B1∪UC_1 B_1∪ U and C3⊆B2∪FC_3 B_2∪ F. Indeed, assuming otherwise, we either have to move some dummy did_i, i∈[2β]i∈[2β], or some candidate in F to the first γ positions, or we have to move some dummy did_i, i∈[2β]i∈[2β], or some candidate in U to the last γ positions. In either case, this requires at least α⋅2βα· 2β swaps in the anchor votes. To see this for the first case, recall that the dummies appear in reverse order in A and in A′A : moving did_i to the first γ positions requires at least i+ki+k swaps in each vote of A, and at least 2β+1−i+k2β+1-i+k swaps in each vote of A′A , amounting to more than α⋅2βα· 2β swaps; the remaining cases are analogous. However, it is not hard to see that d<2α⋅βd<2α·β, a contradiction. Hence, there exists a set U′U of k vertices and a set F′F of (k2) k2 edges such that C1=B1∪U∖U′C_1=B_1∪ U U , C2=U′∪d1,…,d2β∪F′C_2=U ∪\d_1,…,d_2β\∪ F , and C3=B2∪F∖F′C_3=B_2∪ F F . We claim that U′U forms a clique in G with edge set F′F . To see this, notice that the number of swaps necessary can be computed along the same lines as showed earlier; in fact, the choice of U′U and F′F only matters for computing the number of swaps necessary between vertex candidates and edge candidates in incidence votes. Indeed, the number of swaps required to upshift U∖U′U U and downshift F∖F′F F in all votes is exactly 32α⋅β+|F|β+(2|F|−s′) 32α·β+|F|β+(2|F|-s ) where s′s denotes the number of those pairs (f,u)(f,u) for which f∈F′f∈ F , u∈U′u∈ U , and u is an endpoint of f. Since the number of swaps applied must be at most d, we get that s′≥2(k2)s ≥ 2 k2. However, this is only possible if for each f∈F′f∈ F , both endpoints of f are vertices in U′U . By |F′|=(k2)|F |= k2 and |U′|=k|U |=k, this implies that U′U induces a clique of size k in G, as required. This proves the correctness of our reduction. ∎ Next, we show that Nearly SeparationSeparation Election is also intractable. Theorem B.9. The Nearly SeparationSeparation Election problem is NPNP-complete. Proof. Before we present the reduction, we introduce some auxiliary notation. A partition (L,R)(L,R) of C is balanced if |L|=|R|=m/2|L|=|R|= m2. We set L,RD_\L,R\ to be a domain containing all votes where candidates of L are above candidates of R and vice versa. Clearly, L,RD_\L,R\ belongs to the SeparationSeparation family, and we say that L,RD_\L,R\ is specified by (L,R)(L,R). Additionally, we define the rank sum for each voter v and subsets of candidates S⊆CS C as ρv(S)=∑c∈Sposv(c). _v(S)= _c∈ Spos_v(c)\,. Clearly, the rank sum of a set of m/2 m2 candidates is at least ρ¯=1+⋯+m/2 ρ=1+·s+ m2 and at most ρ¯=(m/2+1)+⋯+m ρ=( m2+1)+·s+m. Throughout, we write K=(m/2)2K=( m2)^2. Observe that ρ¯−ρ¯=K ρ- ρ=K and that ρv(L)+ρv(R)=ρ¯+ρ¯ _v(L)+ _v(R)= ρ+ ρ for every voter v∈Vv∈ V and every balanced partition (L,R)(L,R). Now, we show that the distance of a vote v to L,RD_\L,R\ for any balanced partition (L,R)(L,R) can be fully expressed using rank sum. Claim B.10. Let (L,R)(L,R) be a balanced partition of C, and v∈Vv∈ V be a voter. Then min≻∈L,Rdist(v,≻)=minρ¯−ρv(R),ρv(R)−ρ¯. _ _\L,R\dist(v, )= \ ρ- _v(R), _v(R)- ρ\\,. Proof. First, let ≻ be a vote such that all candidates of L are ranked above all candidates of R. We say that a pair of candidates c,d\c,d\ with c∈Lc∈ L and d∈Rd∈ R is dirty if d≻vcd _vc (recall that c≻dc d by our assumption). Then, the distance between v and ≻ is at least x=|(c,d)∈L×R:d≻vc|.x=|\(c,d)∈ L× R d _vc\|\,. Let q1<⋯<qm/2q_1<·s<q_ m2 be the positions of the candidates of R in vote v. Below position qtq_t, there are m−qtm-q_t candidates, out of which m/2−t m2-t belong to R. Therefore, we have x=∑t=1m/2(m−qt−m2+t)=K+ρ¯−ρv(R)=ρ¯−ρv(R),x= _t=1 m2(m-q_t- m2+t)=K+ ρ- _v(R)= ρ- _v(R)\,, where the last equality uses ρ¯−ρ¯=K ρ- ρ=K. Moreover, this bound can be achieved by a vote ≻ which agrees on the internal ordering of L and R with v. Hence, the minimum distance to the votes ranking L above R is exactly ρ¯−ρv(R) ρ- _v(R). Swapping the roles of R and L, the minimum distance to the votes ranking R above L is ρ¯−ρv(L)=ρv(R)−ρ¯ ρ- _v(L)= _v(R)- ρ, where we used ρv(L)+ρv(R)=ρ¯+ρ¯ _v(L)+ _v(R)= ρ+ ρ. ∎ Using the previous claim, we can express the distance of an election E to the SeparationSeparation domain as dist(E,Separation)==min∑v∈V(L,R)minρ¯−ρv(R),ρv(R)−ρ¯.dist(E,Separation)=\\ = _(L,R) _v∈ V \ ρ- _v(R), _v(R)- ρ\\,. (5) This finishes our preparation, and now we prove NPNP-hardness of the problem. We reduce from the Minimum Bisection problem, which is known to be NPNP-complete. In this problem, we are given a graph G=(W,F)G=(W,F) with |W|=2N|W|=2N and an integer k∈ℕk , and the goal is to decide whether W can be partitioned into two parts P1P_1 and P2P_2, each of size N, such that the number of edges with one endpoint in P1P_1 and the other in P2P_2 is at most k. The pair (P1,P2)(P_1,P_2) is called a bisection of G. Without loss of generality, we assume N≥2N≥ 2 and 0≤k<|F|0≤ k<|F|, as otherwise the instance is trivial. Construction. Let ℐ=(G=(W,F),k)I=(G=(W,F),k) be an instance of Minimum Bisection and p be the odd integer p=4N2+1p=4N^2+1. The candidate set C of the constructed instance J consists of W, the vertex candidates, and two sets of dummy candidates D1D_1 and D2D_2, each of size p. We fix an arbitrary ordering over C, and for any candidate set S⊆CS C, we use S→ S to denote the restriction of this ordering to S, and S← S for its reverse. The set of voters consists of several different blocks of voters. First, we create α=|F|⋅Kα=|F|· K copies of two anchor votes a and a′a with a:D1→≻aW→≻aD2→a D_1 _a W _a D_2 and a′:D1→≻a′W←≻a′D2→.a D_1 _a W _a D_2\,. Before we define additional voters, we introduce additional notation. We call position 2N+2p+1−j2N+2p+1-j the mirror of position j. Let d1∈D1d_1∈ D_1 and d2∈D2d_2∈ D_2 be a fixed pair of distinguished dummies and, for each i∈1,2i∈\1,2\, let us fix a guard pair δi=(δi1,δi2) _i=(δ^1_i,δ^2_i) such that δ11,δ12⊆D1∖d1\δ^1_1,δ^2_1\ D_1 \d_1\ and δ21,δ22⊆D2∖d2\δ^1_2,δ^2_2\ D_2 \d_2\. We call positions p+2,…,p+2N−1p+2,…,p+2N-1 the critical positions. For each i∈1,2i∈\1,2\, we define dummy template πi _i, which is a mapping between the dummies in (D1∪D2)∖δi1,δi2(D_1∪ D_2) \ _i^1, _i^2\ and the positions outside the critical positions and 1,2,2N+2p−1,2N+2p\1,2,2N+2p-1,2N+2p\. Specifically, πi _i puts d1d_1 on position r=(p+1)/2r= (p+1)2 and d2d_2 on its mirror; note that 3≤r≤p+13≤ r≤ p+1 since p≥17p≥ 17. The remaining 2p−42p-4 dummies are distributed over the p−2p-2 mirrored position pairs q,2N+2p+1−q:q∈3,…,p+1∖r\\q,2N+2p+1-q\ q∈\3,…,p+1\ \r\\ so that each pair receives two dummies of the same set D1D_1 or D2D_2. The latter is possible: for template πi _i, the numbers of dummies of D1D_1 and of D2D_2 still to be assigned are p−3p-3 and p−1p-1 (for i=1i=1; vice versa for i=2i=2), and both are even because p is odd. Now, we are ready to introduce the edge votes. In particular, for every edge e=u,w∈Fe=\u,w\∈ F and every i∈1,2i∈\1,2\, we introduce the following votes: 11 22 critical 2N+2p−12N+2p-1 2N+2p2N+2p vei,1v_e^i,1 u w W∖u,w→ W \u,w\ δi1 _i^1 δi2 _i^2 vei,2v_e^i,2 δi2 _i^2 δi1 _i^1 W∖u,w← W \u,w\ w u vei,3v_e^i,3 u w W∖u,w← W \u,w\ δi1 _i^1 δi2 _i^2 vei,4v_e^i,4 δi2 _i^2 δi1 _i^1 W∖u,w→ W \u,w\ w u The rest of the votes are filled according to the dummy template πi _i. The election has n=2α+8⋅|F|n=2α+8·|F| voters and |W|+2p|W|+2p candidates. To finalize the construction, we set the budget to d=α⋅N2+|F|⋅(4K−2B)−2(2N+p)⋅(|F|−k),d=α· N^2+|F|·(4K-2B)-2(2N+p)·(|F|-k)\,, where B=4N+4p−4B=4N+4p-4. Next, we show that G has a bisection cutting at most k edges if and only if dist((C,V),Separation)≤ddist((C,V),Separation)≤ d. Additional notation and basic facts. Recall that we have m=2N+2pm=2N+2p. Throughout the analysis, we additionally write M=m+1M=m+1, h=m/2=N+ph= m2=N+p, Q=2N+pQ=2N+p, and ςmax=2(N−1)2 _ =2(N-1)^2; observe that this yields K=h2K=h^2 and d=α⋅N2+|F|⋅(4K−2B)−2Q⋅(|F|−k)d=α· N^2+|F|·(4K-2B)-2Q·(|F|-k). Note that a candidate contributes j to a rank sum when placed on position j, and M−jM-j when placed on its mirror. Furthermore, we use the following two inequalities: ςmax≤p−3and3N2+2N+1≤K. _ ≤ p-3 3N^2+2N+1≤ K\,. (6) The first inequality holds since ςmax<2N2≤p/2≤p−3 _ <2N^2≤ p2≤ p-3, and the second one since K=(N+p)2≥p2≥16N4K=(N+p)^2≥ p^2≥ 16N^4. We say that a balanced partition (L,R)(L,R) of C is aligned if one of its two sides (i.e., either its top or its bottom half) contains all of D2D_2 and no candidate of D1D_1. The two sides of an aligned partition are thus D1∪W1D_1∪ W_1 and D2∪W2D_2∪ W_2 for some partition (W1,W2)(W_1,W_2) of W with |W1|=|W2|=N|W_1|=|W_2|=N; that is, aligned partitions correspond exactly to bisections of G. Vote pairs. Our votes come in pairs that we analyze jointly. First, for any two votes v,v′v,v and any balanced partition (L,R)(L,R), we abbreviate P=ρv(R)+ρv′(R)P= _v(R)+ _v (R) and Δ=ρv(R)−ρv′(R) = _v(R)- _v (R). Expanding the sum of the two minima from Claim B.10 into the minimum of four sums yields min≻∈L,Rdist(v,≻)+min≻∈L,Rdist(v′,≻)=minP−2ρ¯, 2ρ¯−P,K−|Δ|, _ _\L,R\dist(v, )+ _ _\L,R\dist(v , )\\ = \P-2 ρ,\ 2 ρ-P,\ K-| |\\,, (7) where we used (ρv(R)−ρ¯)+(ρ¯−ρv′(R))=K+Δ( _v(R)- ρ)+( ρ- _v (R))=K+ and ρ¯−ρ¯=K ρ- ρ=K. Second, we call (v,v′)(v,v ) a partner pair with flip set X if v′v arises from v by moving every candidate of X from its position to the mirror position, while every other candidate keeps its position. In a partner pair, each candidate c∈X∩Rc∈ X∩ R contributes posv(c)pos_v(c) to ρv(R) _v(R) and M−posv(c)M-pos_v(c) to ρv′(R) _v (R), so P=M⋅|X∩R|+2ρv(R∖X)andΔ=∑c∈X∩R(2posv(c)−M).P=M·|X∩ R|+2 _v(R X) \\ = _c∈ X∩ R(2pos_v(c)-M)\,. (8) Contribution of the anchor votes. Fix a balanced partition (L,R)(L,R) and group the anchor votes into α pairs (a,a′)(a,a ); each of them is a partner pair with flip set X=WX=W. By (8), we have |Δ|≤∑j=p+1p+2N|2j−M|=2⋅(1+3+⋯+(2N−1))=2N2andP=∑c∈Rg(c),| |≤ _j=p+1^p+2N|2j-M|=2·(1+3+·s+(2N-1))=2N^2\\ and P= _c∈ Rg(c)\,, where we define the function g such that g(c)=Mg(c)=M if c is a vertex candidate and g(c)=2posa(c)g(c)=2pos_a(c) if c is a dummy. In the anchor votes, the dummies of D1D_1 have g-values 2,4,…,2p2,4,…,2p, all at most M−(2N+1)M-(2N+1), and the dummies of D2D_2 have g-values 2(2N+p+1),2(2N+p+2),…,2(2N+2p)2(2N+p+1),2(2N+p+2),…,2(2N+2p), all at least M+(2N+1)M+(2N+1). Consequently, over all sets S of h candidates, the sum ∑c∈Sg(c) _c∈ Sg(c) is maximized precisely when D2⊆SD_2 S and S∩D1=∅S∩ D_1= (the rest of S consisting of vertex candidates, whose g-values coincide), and if S misses a dummy of D2D_2 or contains a dummy of D1D_1, then ∑c∈Sg(c)≤P∗−(2N+1) _c∈ Sg(c)≤ P -(2N+1), where P∗P denotes the maximum value. Using M=2h+1M=2h+1, p=h−Np=h-N, and 2ρ¯=2ρ¯+2K=h(h+1)+2h2=3h2+h2 ρ=2 ρ+2K=h(h+1)+2h^2=3h^2+h, a direct computation gives P∗=M⋅N+2⋅∑j=2N+p+12N+2pj=(2h+1)⋅N+(h−N)(3h+N+1)=3h2+h−N2,P =M· N+2· _j=2N+p+1^2N+2pj\\ =(2h+1)· N+(h-N)(3h+N+1)\\ =3h^2+h-N^2\,, and therefore 2ρ¯−P∗=N22 ρ-P =N^2 and P∗−2ρ¯=2K−N2P -2 ρ=2K-N^2. Now, we apply (7). Since ρa(L)+ρa(R)=ρ¯+ρ¯ _a(L)+ _a(R)= ρ+ ρ holds for each anchor vote, we have P−2ρ¯=2ρ¯−∑c∈Lg(c)P-2 ρ=2 ρ- _c∈ Lg(c), so both of the first two terms in (7) are of the form 2ρ¯−∑c∈Sg(c)2 ρ- _c∈ Sg(c) with S∈L,RS∈\L,R\. If (L,R)(L,R) is aligned, then one of its sides attains P∗P , so the pair (a,a′)(a,a ) costs min2K−N2,N2,K−|Δ|=N2 \2K-N^2,\ N^2,\ K-| |\=N^2 exactly—irrespective of how the vertex candidates are split—because K−|Δ|≥K−2N2≥N2+2N+1K-| |≥ K-2N^2≥ N^2+2N+1 by (6). If (L,R)(L,R) is not aligned, then each of its two sides misses a dummy of D2D_2 or contains a dummy of D1D_1, so the first two terms in (7) are at least 2ρ¯−P∗+(2N+1)=N2+2N+12 ρ-P +(2N+1)=N^2+2N+1; moreover K−|Δ|≥K−2N2≥N2+2N+1K-| |≥ K-2N^2≥ N^2+2N+1 by (6), as before. Hence, the pair costs at least N2+2N+1N^2+2N+1. Contribution of the edge votes under aligned partitions. Let (L,R)(L,R) be an aligned partition with D1⊆LD_1 L and D2⊆RD_2 R (the roles of the two sides being interchangeable), and let W1=W∩LW_1=W∩ L and W2=W∩RW_2=W∩ R. Fix an edge e=u,w∈Fe=\u,w\∈ F and a template i∈1,2i∈\1,2\. Both (vei,1,vei,2)(v_e^i,1,v_e^i,2) and (vei,3,vei,4)(v_e^i,3,v_e^i,4) are partner pairs with flip set X=W∪δi1,δi2X=W∪\ _i^1, _i^2\: positions 11 and 22 are the mirrors of positions 2N+2p2N+2p and 2N+2p−12N+2p-1, respectively, the critical positions are closed under mirroring, and the template dummies keep their positions. We first compute P, which is the same for both pairs. The fixed candidates of R, i.e., R∖XR X, are exactly the template dummies of D2D_2: the distinguished dummy d2d_2 sits on the mirror of position r and contributes M−rM-r to ρvei,1(R∖X) _v_e^i,1(R X), and each same-set pair of D2D_2-dummies occupies two mirrored positions and contributes M; the number of such pairs is (p−1)/2 (p-1)2 for i=1i=1 and (p−3)/2 (p-3)2 for i=2i=2. The flipping candidates of R number |X∩R|=|W2|=N|X∩ R|=|W_2|=N for i=1i=1 and |X∩R|=N+2|X∩ R|=N+2 for i=2i=2—in every case, as the vertices u and w are already counted in W2W_2 if they lie in R. Hence, by (8), in all cases P=M⋅(N+p+1)−2r=M⋅(h+1)−(p+1),P=M·(N+p+1)-2r=M·(h+1)-(p+1)\,, where we used 2r=p+12r=p+1. Consequently, by 2ρ¯=h(h+1)2 ρ=h(h+1) and 2h−p=Q2h-p=Q, we obtain P−2ρ¯=(h+1)2−(p+1)=K+QP-2 ρ=(h+1)^2-(p+1)=K+Q and 2ρ¯−P=2K−(K+Q)=K−Q.2 ρ-P=2K-(K+Q)=K-Q\,. Next, we compute the differences Δ . Let ς=∑c∈W2∖u,w(2posvei,1(c)−M), = _c∈ W_2 \u,w\(2pos_v_e^i,1(c)-M)\,, so |ς|≤∑j=p+2p+2N−1|2j−M|=2⋅(1+3+⋯+(2N−3))=ςmax,| |≤ _j=p+2^p+2N-1|2j-M|=2·(1+3+·s+(2N-3))= _ \,, and the corresponding quantity for the pair (vei,3,vei,4)(v_e^i,3,v_e^i,4) is −ς- , since there the critical positions carry W∖u,w← W \u,w\. By (8), the two pairs of template i have Δ=ci+ς =c_i+ and Δ=ci−ς =c_i- , respectively, where cic_i collects the terms 2posvei,1(c)−M2pos_v_e^i,1(c)-M of u, w, and the guard pair δi _i insofar as they lie in R: vertex u (of rank 11) contributes −(2N+2p−1)-(2N+2p-1) if u∈Ru∈ R, vertex w (of rank 22) contributes −(2N+2p−3)-(2N+2p-3) if w∈Rw∈ R, and the guard pair δ2⊆D2⊆R _2 D_2 R (whose candidates rank 2N+2p−12N+2p-1 and 2N+2p2N+2p, and are contained in X only for i=2i=2) contributes (2N+2p−3)+(2N+2p−1)=B(2N+2p-3)+(2N+2p-1)=B. Explicitly: u∈Lu∈ L u∈Ru∈ R u∈Ru∈ R u∈Lu∈ L w∈Lw∈ L w∈Rw∈ R w∈Lw∈ L w∈Rw∈ R c1c_1 00 −B-B −(2N+2p−1)-(2N+2p-1) −(2N+2p−3)-(2N+2p-3) c2c_2 B 00 2N+2p−32N+2p-3 2N+2p−12N+2p-1 By (7), the two pairs of template i cost K−maxQ,|ci+ς|K- \Q,|c_i+ |\ and K−maxQ,|ci−ς|K- \Q,|c_i- |\, respectively. From ςmax≤p−3 _ ≤ p-3 in (6), we get both ςmax<Q and (2N+2p−3)−ςmax≥2N+p=Q _ <Q and (2N+2p-3)- _ ≥ 2N+p=Q (and a fortiori (2N+2p−1)−ςmax≥Q(2N+2p-1)- _ ≥ Q and B−ςmax≥QB- _ ≥ Q). If e is not cut by the bisection (W1,W2)(W_1,W_2), then ci=0c_i=0 for exactly one of the two templates; since |±ς|≤ςmax<Q|± |≤ _ <Q, its two pairs cost K−QK-Q each. For the other template, we have |ci|=B|c_i|=B, and its two pairs cost (K−(B−ς))+(K−(B+ς))=2K−2B(K-(B- ))+(K-(B+ ))=2K-2B in total. Altogether, the eight votes of an uncut edge cost exactly (2K−2Q)+(2K−2B)=4K−2B−2Q.(2K-2Q)+(2K-2B)=4K-2B-2Q\,. If e is cut, then |c1|,|c2|=2N+2p−1, 2N+2p−3\|c_1|,|c_2|\=\2N+2p-1,\ 2N+2p-3\, and the four pairs cost ∑i∈1,2((K−(|ci|−ς))+(K−(|ci|+ς)))=4K−2(2N+2p−1)−2(2N+2p−3)=4K−2B _i∈\1,2\ ((K-(|c_i|- ))+(K-(|c_i|+ )) )\\ =4K-2(2N+2p-1)-2(2N+2p-3)\\ =4K-2B in total. Thus, a cut edge costs exactly 2Q2Q more swaps than an uncut one, and for every aligned partition (L,R)(L,R), we obtain ∑v∈Vmin≻∈L,Rdist(v,≻)==α⋅N2+|F|⋅(4K−2B)−2Q⋅(|F|−t) _v∈ V _ _\L,R\dist(v, )=\\ =α· N^2+|F|·(4K-2B)-2Q·(|F|-t) (9) where t is the number of edges of G cut by the bisection (W1,W2)(W_1,W_2). ℐI is a yes-instance ⇒ J is a yes-instance. Suppose G admits a bisection (P1,P2)(P_1,P_2) cutting t≤kt≤ k edges, and consider the aligned partition (D1∪P1,D2∪P2)(D_1∪ P_1,\ D_2∪ P_2); it is balanced because |D1|=|D2||D_1|=|D_2| and |P1|=|P2||P_1|=|P_2|. By (5) and (9), we obtain dist((C,V),Separation)≤α⋅N2+|F|⋅(4K−2B)−2Q⋅(|F|−t)≤d.dist((C,V),Separation)≤\\ ≤α· N^2+|F|·(4K-2B)-2Q·(|F|-t)≤ d\,. J is a yes-instance ⇒ ℐI is a yes-instance. Suppose dist((C,V),Separation)≤ddist((C,V),Separation)≤ d, and let (L,R)(L,R) be a balanced partition attaining the minimum in (5). First, assume for the sake of contradiction that (L,R)(L,R) is not aligned. Since every summand in (5) is non-negative and each of the α anchor pairs costs at least N2+2N+1N^2+2N+1, we get dist((C,V),Separation) ((C,V),Separation) ≥α⋅(N2+2N+1) ≥α·(N^2+2N+1) >α⋅N2+4K⋅|F|≥d >α· N^2+4K·|F|≥ d where the strict inequality holds because α⋅(2N+1)=|F|⋅K⋅(2N+1)≥5⋅|F|⋅K>4K⋅|F|α·(2N+1)=|F|· K·(2N+1)≥ 5·|F|· K>4K·|F| by the choice of α and the assumption N≥2N≥ 2, a contradiction. Therefore, (L,R)(L,R) is aligned, say with D1⊆LD_1 L, and (W∩L,W∩R)(W∩ L,\ W∩ R) is a bisection of G; let t be the number of edges it cuts. By (9), we have α⋅N2+|F|⋅(4K−2B)−2Q⋅(|F|−t)==dist((C,V),Separation)≤dα· N^2+|F|·(4K-2B)-2Q·(|F|-t)=\\ =dist((C,V),Separation)≤ d which, by the definition of d, yields t≤kt≤ k. This means that (W∩L,W∩R)(W∩ L,W∩ R) is a bisection of G cutting at most k edges, which completes the proof. ∎ B.5 Proof of Theorem 3.5 See 3.5 Proof. We reduce from the Minimum Feedback Arc Set (FAS) problem, whose input is a directed graph D and an integer k∈ℕk , and the task is to decide whether D contains a set of k arcs whose deletion from D yields an acyclic directed graph. We first create the duplicate D′D , i.e, the disjoint union of two copies of D. Next, using the method described by Bachmeier et al. (2019), we reduce the instance (D′,2k)(D ,2k) of FAS to an equivalent instance (D′,2k)(D ,2k) in which the digraph D′D is induced by an election E with 44 voters over the vertices of D′D , meaning that the majority digraph of E is D′D ; such an election E can be constructed in polynomial time. Since D′D is obtained by subdividing each arc of D′D exactly once, the vertices in D′D can still be partitioned into two sets U=u1,…,umU=\u_1,…,u_m\ and U′=u1′,…,um′U =\u _1,…,u _m\ such that D′D is the disjoint union of the two isomorphic subgraphs of D′D induced by U and U′U , with ui′u _i being the copy of uiu_i for each i∈[m]i∈[m]. Moreover, the construction for E ensures the property that for each arc (v,w)(v,w) present in D′D , exactly three voters prefer v to w. We set the budget as d=2(2m2)−2m−|A|+4kd=2 2m2-2m-|A|+4k where A is the arc set of D′D . First, assume that D′D admits a minimal feedback arc set of size at most 2k2k. Clearly, such a solution must contain a set S of at most k arcs from D′[U]D [U] and a set S′S of |S||S| arcs from D′[U′]D [U ], because these two digraphs are isomorphic—in fact, we may assume that each arc in S′S is a copy of one in S. Let ui1,…,uimu_i_1,…,u_i_m be a topological ordering of the graph obtained from D′[U]D [U] by deleting the arcs in S, and let TmT_m be a PQFPQF-tree with m leaves representing the m/2-Stratificationm/2- domain. We are going to show that E has distance at most d from (Tm,(ui1,ui1′,…,uim,uim′))D(T_m,(u_i_1,u _i_1,…,u_i_m,u _i_m)). Note that for each i∈[m]i∈[m], candidates uiu_i and ui′u _i need not be swapped in any of the votes, because they correspond to the two children of a PP-node in TmT_m. By contrast, for each arc f=(ui,uj)∈A∩(U×U)f=(u_i,u_j)∈ A∩(U× U), we perform the following steps: If f∉Sf∉ S, then we know that uiu_i precedes uju_j in the topological ordering, so we need to swap uiu_i and uju_j in the unique vote that ranks uju_j before uiu_i. This amounts to |A|2−|S| |A|2-|S| swaps. If f∈Sf∈ S, then by the minimality of S, we know that uju_j must precede uiu_i in the topological ordering, so we need to swap these candidates in all three votes that rank uiu_i before uju_j, yielding 3⋅|S|3·|S| swaps. We need the same number of swaps for arcs in A∩(U′×U′)A∩(U × U ). Finally, for each pair of vertices in D′D that are not connected by an arc but are not formed by a vertex in U and its copy, we need to swap the corresponding candidates in exactly two votes. Thus, the total number of swaps used is 2(|A|2−|S|+3⋅|S|)+2((2m2)−m−|A|)=2(2m2)−2m+4|S|−|A|≤d2 ( |A|2-|S|+3·|S| )+2 ( 2m2-m-|A| )\\ =2 2m2-2m+4|S|-|A|≤ d due to |S|≤k|S|≤ k. This proves that the constructed election E (whose majority digraph is D′D ) has swap distance at most d from (Tm,(ui1,ui1′,…,uim,uim′))D(T_m,(u_i_1,u _i_1,…,u_i_m,u _i_m)). Assume now that E has swap distance at most d from some election E~ E in the m/2-Stratificationm/2- domain. Then E~ E is in (Tm,(v1,…,v2m))D(T_m,(v_1,…,v_2m)) for some ordering σ=v1,…,v2mσ=v_1,…,v_2m of the vertex set U∪U′U∪ U of D′D ; note that for each vertex in U∪U′U∪ U we use an alias vjv_j that encodes its position in σ. We may assume that for each i∈[m]i∈[m] we have (v2i,v2i−1)∉A(v_2i,v_2i-1)∉ A, as otherwise we can simply switch these two candidates in the ordering σ without changing the domain. Let A⋆A denote the set of arcs in A of the form (v2i−1,v2i)(v_2i-1,v_2i) for some i∈[m]i∈[m]. Let S contains those arcs (vi,vj)(v_i,v_j) where vjv_j precedes viv_i in σ (i.e., the “backward” arcs for σ). Note that S∩A⋆=∅S∩ A = , and all arcs in A∖SA S point from some vjv_j to vj′v_j with j<j′j<j and thus form an acyclic digraph. Thus, S is a feedback arc set for D′D . We will show that |S|≤2k|S|≤ 2k. To see this, we compute the number of swaps necessary to turn E into an election in (Tm,(v1,…,v2m))D(T_m,(v_1,…,v_2m)) as follows. First, for each arc in S, its endpoints must be swapped in three votes, yielding 3⋅|S|3·|S| swaps. For each arc in A∖A⋆∖SA A S, we need to swap the endpoint candidates in exactly one vote. Finally, each pair of vertices in D′D that are not connected by an arc and are not of the form v2i−1,v2i\v_2i-1,v_2i\ for some i∈[m]i∈[m] must be swapped in exactly two votes; the number of such candidate pairs is (2m2)−|A|−(m−|A⋆|) 2m2-|A|-(m-|A |), because there are (2m2)−|A| 2m2-|A| non-arcs in D′D and exactly m−|A⋆|m-|A | of them are of the form v2i−1,v2i\v_2i-1,v_2i\. Thus, the number of swaps necessary is 3⋅ 3· |S|+|A∖A⋆∖S|+2((2m2)−|A|−m+|A⋆|) |S|+|A A S|+2 ( 2m2-|A|-m+|A | ) =2⋅|S|−|A|+2(2m2)+|A⋆|−2m =2·|S|-|A|+2 2m2+|A |-2m =d−4k+2⋅|S|+|A⋆|≤d =d-4k+2·|S|+|A |≤ d which implies |S|≤2k−|A⋆|2≤2k|S|≤ 2k- |A |2≤ 2k, as required. Hence, S is a solution to our instance (D′,2k)(D ,2k) of FAS, proving the correctness of the reduction. ∎ B.6 Proof of Theorem 3.6 See 3.6 Proof. We show NPNP-hardness by reduction from the Kemeny Aggregation problem. Let the input instance of Kemeny Aggregation consist of an election E=(C,V)E=(C,V) with C=c1,c2,…,cmC=\c_1,c_2,…,c_m\ and V=(v1,v2,…,vn)V=(v_1,v_2,…,v_n), and a budget d. We create a new election E′=(C′,V′)E =(C ,V ) over C′=C∪c1′,c2′,…,c2d+2′C =C∪\c_1 ,c_2 ,…,c_2d+2 \ by simply appending the 2d+22d+2 new candidates in a fixed order at the end of each vote, i.e., for each vi∈Vv_i∈ V we create a corresponding vote vi′v_i by vi′=(vi,c1′,c2′,…,c2d+2′),v_i =(v_i,c_1 ,c_2 ,…,c_2d+2 ), and set V′=(v1′,…,vn′)V =(v_1 ,…,v_n ). We claim that E′E has distance at most d from some AntagonismAntagonism domain if and only if (E,d)(E,d) is a yes-instance of Kemeny Aggregation. Direction “⇒ ”. Assume (E,d)(E,d) is a yes-instance of the Kemeny Aggregation problem. Then there is some common ordering v∗∈ℒ(C)v^* (C) which has total swap distance at most d from all votes in V. In consequence, E′E is swap distance at most d from the AntagonismAntagonism domain that contains the vote (v∗,c1′,c2′,…,c2d+2′)(v^*,c_1 ,c_2 ,…,c_2d+2 ) and its reverse. Direction “⇐ ”. Suppose that E′E has swap distance at most d from some election E′E in the AntagonismAntagonism domain. Since each vote of E′E can be obtained from some vote in V′V by at most d swaps, candidate c2d+2′c _2d+2 appears in the bottom half of each vote of E′E . Hence, E′E cannot contain both some vote and its reverse, i.e., each vote in E′E is a copy of the same vote u. Considering only swaps among candidates in C, this means that we can transform each vote in V into u↾Cu_ _C using a total of at most d swaps. Thus, (E,d)(E,d) is a yes-instance of Kemeny Aggregation. As Kemeny Aggregation is NPNP-hard for 4 voters, the result for n=4n=4 follows. ∎ B.7 NPNP-completeness of Nearly Single-CrossingSingle- Election In their paper, Lakhani, Peters, and Elkind (2019) claim that their reduction (Lakhani, Peters, and Elkind 2019, Theorem 1) proving the NPNP-hardness of computing the swap distance to a single-crossing election with a fixed ordering of voters “can easily be extended to the setting where voters can be permuted.” However, they left the claim without a formal proof, and we do not find the extension entirely trivial. Therefore, we formally prove that it is indeed the case by our own proof, building on the reduction of Lakhani, Peters, and Elkind (2019, Theorem 1). Proposition B.11. Nearly Single-CrossingSingle- Election is NPNP-complete. Proof. We reduce from the NPNP-complete problem called Global Swaps in (Lakhani, Peters, and Elkind 2019). The input of this problem is an election E=(C,V)E=(C,V) with the votes in V ordered as v1,…,vnv_1,…,v_n, and an integer d. Its task is to decide whether there exists an election (C,(v1′,…,vm′))(C,(v_1 ,…,v_m )) with ∑i∈[n]dist(vi,vi′)≤d _i∈[n]dist(v_i,v _i)≤ d that is single-crossing with respect to the given ordering of its votes. We construct an equivalent instance of Nearly Single-CrossingSingle- Election as follows. For each i∈[n−1]i∈[n-1], we add a set AiA_i of d+2d+2 dummy candidates, and we fix an ordering over them. Next, for each i∈[n]i∈[n], we create a vote v^i v_i by appending these dummies at the end of the vote viv_i as below: v^1 v_1 :v1,A1→,…,An−1→; :v_1, A_1,…, A_n-1; v^i v_i :vi,A1←,…,Ai−1←,Ai→,…,An−1→ for 1<i<m; :v_i, A_1,…, A_i-1, A_i,…, A_n-1 for $1<i<m$; v^n v_n :vn,A1←,…,An−1←. :v_n, A_1,…, A_n-1. Let OPENE^=(C∪A1∪⋯∪An−1),V^) E=(C∪ A_1∪…∪ A_n-1), V) be the obtained election where V^=(v^1,…,v^n) V=( v_1,…, v_n). We finish the construction by setting the budget as d. First, if (E,d)(E,d) is a yes-instance of Global Swaps, then it is clear that (E^,d)( E,d) is a yes-instance of Nearly Single-CrossingSingle- Election: applying the same swaps that turn E into a single-crossing election with respect to the given ordering of the votes trivially turns E E as well into a single-crossing election. For the other direction, assume that there is an election E′E within swap distance at most d from E E that is single-crossing with respect to some ordering σ of the votes. For each i∈[n]i∈[n], let v^i′ v _i denote the vote in E′E obtained from v^i v_i. Since v^i′ v _i can be obtained from v^i∈V v_i∈ V using at most d swaps, the first and last dummies in Aj→ A_j, say aj1a_j^1 and ajd+2a_j^d+2, for each j∈[n−1]j∈[n-1] must retain their ranking as determined by v^i v_i, because swapping them in v^i v_i would require at least d+1d+1 swaps. This means that for each j∈[n−1]j∈[n-1], either all votes in v^1′,…,v^j−1′\ v _1,…, v _j-1\ precede all votes in v^j′,…,v^n′\ v _j,…, v _n\ in σ or vice versa, as otherwise aj1a_j^1 and ajd+2a_j^d+2 would cross at least twice in the ordering σ of the votes. Therefore, σ must order all votes of E′E either in the order v^1′,…,v^n′ v _1,…, v _n or in the order v^n′,…,v^1′ v _n,…, v _1. Since the single-crossing domain with respect to these two orderings coincide, we obtain that E′E is, in fact, single-crossing with respect to the ordering v^1′,…,v^n′ v _1,…, v _n of the voters. Thus, restricting E′E to C yields an election within swap distance at most d from E that is single-crossing with respect to the prescribed ordering of the votes, showing that (E,d)(E,d) is a yes-instance of Global Swaps. ∎ Appendix C Additional material for Section 4.1 In this section, we present all omitted proofs for our algorithmic results that consider the number of candidates as a parameter. C.1 Proof of Theorem 4.2 See 4.2 Proof. Let X be a family of domains over a set C of m candidates that can be represented by a family T of PQFPQF-trees. The number of PQFPQFtrees in such a family T is at most c(m)c^O (m ) for some constant c. Therefore, we can enumerate all trees T∈T and, for each such tree T, try all possible bijections φ from C to the leaves of T. Then, in (m!)O (m! ) time, we compute all votes in (T,φ)D(T, ), and for each vote in the input election E we find the closest vote in (T,φ)D(T, ) in |(T,φ)|⋅(m2n)|D(T, )|·O (m^2n ) time. This enables us to compute dist(E,(T,φ))dist(E,D(T, )). There are m!=2(m⋅logm)m!=2^O (m· m ) possible bijections φ for every T, so the overall running time of the algorithm is c(m)⋅(m!)⋅(m!)⋅(m2n)=2(mlogm)⋅n,c^O (m )·O (m! )·O (m! )·O (m^2n )=2^O (m m )· n, which is clearly in FPTFPT. The algorithm is correct, as we try all maximal elections in any domain over C belonging to X. ∎ C.2 Proof of Theorem 4.3 See 4.3 Proof. The algorithm is based on dynamic programming over all subsets of candidates. Formally, we have a table DP[X]DP[X], where X⊆CX C, which stores the distance to an optimal election E′∈GSE for an election (X,V)(X,V), where V is a list of the original votes restricted only to candidates in X. Once the dynamic programming table is computed, we simply compare the value stored in DP[C]DP[C] and compare it with the budget d. By definition, the stored value is the distance from the closest election E′∈GSE , so the result is correct, assuming that the table is filled correctly. Now, we formally describe how to compute each cell of the table. First, assume that |X|≤2|X|≤ 2. Then, there is exactly one possible QQ-tree T and two possible bijections from X to the leaves of T, both with distance 00 from (X,V)(X,V). Therefore, in this case, we set DP[X]=0.DP[X]=0. Now, let |X|≥3|X|≥ 3. In this case, we try all possible partitionings of X between the left and right subtrees. Note that there are 2|X|−22^|X|-2 possibilities (putting all candidates to the left or right subtree is an invalid partitioning). We denote by L the subset of X in the left subtree and by R the subset of X for the right subtree, i.e., R=X∖LR=X L. Now, for every vote v∈Vv∈ V, in (m)O (m ) time, we can compute the value δv,L,X _v,L,X: the minimum number of swaps required to have all candidates in L either as the top |L||L| candidates in v↾Xv_ _X or the bottom |L||L| candidates in v↾Xv_ _X (we take a smaller of these two values), and then use recursion on the subelections induced by L and R. Formally, the computation is as follows. DP[X]=min∅⊂L⊂X∑v∈Vδv,L,X+DP[L]+DP[X∖L].DP[X]= _ ⊂ L⊂ X \ _v∈ V _v,L,X+DP[L]+DP[X L] \. The total time required to fill the table is ∑X⊆C(2|X|−1)⋅(mn) _X C(2^|X|-1)·O (mn ) =(mn)⋅∑k=0m(mk)⋅2k =O (mn )· _k=0^m mk· 2^k =(mn)⋅(1+2)m =O (mn )·(1+2)^m =(mn)⋅3m. =O (mn )· 3^m. After the table is filled, we can decide the instance in constant time. ∎ C.3 Proof of Theorem 4.4 See 4.4 Proof. We use the dynamic programming approach described in Theorem 4.3, tailored to the specific domain family at hand; we re-use the notation described in the proof of Theorem 4.3. First, let =GS/catX=GS/ . Here, the computation for any set X⊆CX C of size at least 33 reduces to the following. DP[X]=minc∈X∑v∈Vδv,L,X+DP[X∖c].DP[X]= _c∈ X \ _v∈ V _v,L,X+DP[X \c\] \. That is, each cell can be computed in (mn)O (mn ) time. Therefore, as there are 2m2^m cells in total, we directly obtain the running time of 2m⋅(mn)2^m·O (mn ). If =GS/balX=GS/ , then the base case is again the same. However, the computation for X⊆CX C is modified. First, we can optimize by fixing r∈Xr∈ X, which always goes to L. This is due to the fact that in perfect binary QQ-trees, the distinction between left and right child is not important. This saves half of the possible partitions. Formally, the computation is as follows. DP[X]=minL⊆X|L|=|X|/2r∈L∑v∈Vδv,L,X+DP[L]+DP[X∖L].DP[X]= _ subarraycL X\\ |L|=|X|/2\\ r∈ L subarray \ _v∈ V _v,L,X+DP[L]+DP[X L] \\,. Moreover, observe that we need to consider only sets X such that |X|=2k|X|=2^k for some k∈ℕk . The DP table has entries for all X⊆CX C with |X|=2j|X|=2^j for j∈0,1,…,log2mj∈\0,1,…, _2m\. For |X|≤2|X|≤ 2, the cost is (1)O (1 ). For |X|=2j|X|=2^j with j≥2j≥ 2, we enumerate (2j−12j−1−1) 2^j-12^j-1-1 partitions (fixing r∈Lr∈ L), and each partition costs (2j⋅n)O (2^j· n ) to evaluate ∑v∈Vδv,L,X _v∈ V _v,L,X. The total running time is therefore ∑j=2log2m _j=2 _2m (m2j)⋅(2j−12j−1−1)⋅(2j⋅n) m2^j· 2^j-12^j-1-1·O (2^j· n ) =(m⋅n)⋅∑j=2log2m(m2j)(2j2j−1) =O (m· n )· _j=2 _2m m2^j 2^j2^j-1 =((22)m⋅m⋅n), =O ((2 2)^m· m· n )\,, where the last step uses that the sum ∑j(m2j)(2j2j−1) _j m2^j 2^j2^j-1 is dominated by its j=log2m−1j= _2m-1 term, which is (23m/2)O (2^3m/2 ) by Stirling’s approximation. Thus, the algorithm runs in ((22)m⋅m⋅n)O ((2 2)^m· m· n ) time. If =SeparationX=Separation, we do the following. We guess the subset L⊆CL C, |L|=|C|/2|L|=|C|/2, of candidates in the left part, and for each such guess, we compute δv,L _v,L which is the swap distance of v from the SeparationSeparation domain corresponding to L. Overall, the running time is (2m⋅m⋅n)O (2^m· m· n ). Finally, let =k-StratificationX=k- for a given k≥2k≥ 2 with k|mk m, and let b=m/kb= mk be the block size. Recall that each domain in k-Stratification(C)k- (C) is given by an ordered partition of C into k blocks of size b: its votes rank all candidates of the first block on top, in an arbitrary order, then all candidates of the second block, and so on. The table now has a cell DP[X]DP[X] for every X⊆CX C whose size is divisible by b; it stores the distance of the election (X,V↾X)(X,V_ _X) to the family of domains given by ordered partitions of X into |X|/b |X|b blocks of size b. Since within a single block the votes are unconstrained, we set DP[X]=0DP[X]=0 for |X|≤b|X|≤ b. For |X|≥2b|X|≥ 2b, we try all possible topmost blocks, i.e., all sets B⊆XB X with |B|=b|B|=b. For every vote v∈Vv∈ V, in (m)O (m ) time we can compute the value δv,B,X↑δ _v,B,X: the minimum number of swaps required to have all candidates in B as the top |B||B| candidates in v↾Xv_ _X, which equals the number of pairs consisting of a candidate of B and a candidate of X∖BX B that v↾Xv_ _X ranks above it. In contrast to the previous cases, the reversed placement is not available, as the root is of type FF and not QQ. Formally, the computation is as follows. DP[X]=minB⊆X|B|=b∑v∈Vδv,B,X↑+DP[X∖B].DP[X]= _ subarraycB X\\ |B|=b subarray \ _v∈ Vδ _v,B,X+DP[X B] \. The recurrence is correct, as each pair of candidates from two different blocks is charged exactly once, namely in the cell in which the block of its higher-ranked member is chosen as B, whereas pairs within a single block are never charged. Using (mjb)(jb)=(mb)(m−b(j−1)b) mjb jbb= mb m-b(j-1)b, the total time required to fill the table is ∑X⊆Cb||X|(|X|b)⋅(mn)=(mn)⋅(mb)∑j≥1(m−b(j−1)b)≤(mn)⋅(mb)⋅2m−b=(3m⋅mn), _ subarraycX C\\ b\, \,|X| subarray |X|b·O (mn )=O (mn )· mb _j≥ 1 m-b(j-1)b\\ ≤O (mn )· mb· 2^m-b=O (3^m· mn )\,, where we use (mb)2m−b≤∑s=0m(ms)2m−s=3m mb2^m-b≤ _s=0^m ms2^m-s=3^m in the last equality. For m/2-Stratificationm/2- , that is, for b=2b=2, we have (mb)2m−b=(2m2) mb2^m-b=O (2^mm^2 ), and hence the running time becomes (2m⋅m3n)O (2^m· m^3n ). ∎ C.4 Proof of Observation 4.5 See 4.5 Proof. As our first step, we guess the axis ⊳ of a closest single-peaked election. Next, we generate the set of all votes V′V compatible with the guessed axis ⊳ . Then, for each vote v∈Vv∈ V, we find the closest vote v′∈V′v ∈ V by enumeration. Finally, we compare ∑v∈Vdist(v,v′) _v∈ Vdist(v,v ) with d. If the sum is smaller than d, we return yes. Otherwise, we continue with another axis ⊳ . If we exhausted all axes without finding a solution, we return no. There are m!∈m∈2(mlogm)m!∈ m^m∈ 2^O (m m ) different axes. There are 2m−12^m-1 votes corresponding to a fixed axis; therefore, we can compute the closest votes in time n⋅2m−1⋅m(1)n· 2^m-1· m^O (1 ). Hence, the algorithm runs in 2(mlogm)⋅n2^O (m m )· n time. ∎ C.5 Proof of Theorem 4.6 See 4.6 Proof. As our first step, we guess the domain ′D of a closest single-crossing election, as follows. We guess a vote u0∈ℒ(C)u_0∈L(C), initialize ′:=u0D :=\u_0\ and u:=u0u:=u_0, and repeat the following (m2) m2 times: We guess two candidates that are adjacent in u and that u orders in the same way as u0u_0 does, we swap them in u, and we add the resulting vote to ′D . Next, for each vote v∈Vv∈ V, we find, a closest vote v′∈′v by enumeration. Finally, we compare ∑v∈Vdist(v,v′) _v∈ Vdist(v,v ) with d. If the sum is at most d, we return yes. Otherwise, we continue with the next guess. If we exhausted all guesses without finding a solution, we return no. To analyze the procedure, we relabel the candidates so that u0u_0 becomes the identity permutation; then the pairs of candidates that a vote orders differently than u0u_0 become its inversions, and containment of inversion sets defines the weak Bruhat order on ℒ(C)L(C). This order is graded by the number of inversions, its maximum element is the reverse of u0u_0, and u′u covers u exactly if u′u arises from u by swapping two candidates that are adjacent in u and ordered as in u0u_0; we refer to Bjorner and Brenti (2005, Chapter 3) for these facts. Hence, each step of our procedure moves from u to a cover of u, and such a cover exists as long as u is not the maximum element, and after (m2) m2 steps the maximum is reached; so the procedure is well-defined, and the guessed sets ′D are exactly the maximal chains of the weak Bruhat order. Further, a domain is single-crossing if and only if, for one of its votes t1t_1, the sets of pairs on which its votes disagree with t1t_1 are pairwise nested (Jaeckle, Peters, and Elkind 2018, Proposition 1), that is, if and only if it is a chain of the weak Bruhat order relabeled so that t1t_1 is the identity. In particular, every guessed ′D is a single-crossing domain (these maximal chains are known in social choice as the maximal single-crossing domains (Puppe and Slinko 2019)); consequently, whenever we return yes, replacing each vote v by v′v turns E into a single-crossing election using at most d swaps. Conversely, suppose that dist(E,Single-Crossing)≤ddist(E,Single- )≤ d, witnessed by a domain ∈Single-Crossing(C)D - (C) with first vote t1t_1 as above. Then D is a chain of the weak Bruhat order relabeled at t1t_1, and every chain of a finite partial order is contained in a maximal one; so some ′D guessed for u0=t1u_0=t_1 satisfies ⊆′D . Then, for every vote v, we have minw∈′dist(v,w)≤minw∈dist(v,w) _w dist(v,w)≤ _w dist(v,w), so the sum of computed distances from ′D is at most dist(E,)≤ddist(E,D)≤ d, and we return yes. There are m!m! possibilities for the initial vote u0u_0 and at most m−1m-1 possibilities for the swapped pair in each of the (m2) m2 steps; therefore, there are m!⋅(m−1)(m2)∈2(m2logm)m!·(m-1) m2∈ 2^O (m^2 m ) guesses in total. There are (m2)+1 m2+1 votes in a fixed guessed domain; therefore, we can compute the closest votes in n⋅m(1)n· m^O (1 ) time per guess. Hence, the algorithm runs in 2(m2logm)⋅n2^O (m^2 m )· n time. ∎ Appendix D Additional material for Section 4.2 In this section, we present all omitted proofs for our algorithmic results that consider the distance budget d as the parameter. In Theorem D.4, we also present an alternative algorithm to solve the Nearly GSGS Election problem—running in FPTFPT time with d as the parameter—that proved to be efficient in practice, even though its worst-case running time is dominated by the one showed in Corollary 4.8 which relies on the characterization of GSGS domains through forbidden partial subelections. In addition, we also present a proof showing that IdentityIdentity and AntagonismAntagonism domains are hereditary (Proposition D.17). D.1 Proof correctness for Theorem 4.7 We prove the correctness of the algorithm, described in the main text, in a series of claims. Claim D.1. Let ℛR be a state in which every tournament TiT_i is acyclic. Then for every voter viv_i, the vote v^i v_i disagrees with viv_i exactly on the pairs in RiR_i. Consequently, E E is admissible for ℛR and at swap distance exactly ∑i|Ri| _i|R_i| from E, and every election admissible for ℛR agrees with E E on all pairs in RiR_i, i∈[n]i∈[n]. Proof. The vote v^i v_i is the unique linear extension of the transitive tournament TiT_i, so it realizes every arc of TiT_i: it inverts, relative to viv_i, all pairs in RiR_i, and it orders every pair outside RiR_i as viv_i does, by construction of TiT_i. Hence, v^i v_i disagrees with viv_i exactly on RiR_i, so E E is admissible and ∑idist(vi,v^i)=∑i|Ri| _idist(v_i, v_i)= _i|R_i|. Finally, any vote admissible for RiR_i inverts every pair in RiR_i relative to viv_i, and so does v^i v_i; hence, the two agree on all pairs in RiR_i. ∎ Claim D.2. Whenever f(ℛ)=d′≠∞f(R)=d ≠∞, we have d′≤d ≤ d and there is an election in D admissible for ℛR at swap distance exactly d′d from E. Proof. We proceed by induction over d−∑i|Ri|d- _i|R_i|. If the algorithm computes f(ℛ)f(R) directly and f(ℛ)=d′f(R)=d is finite, then d′=∑i|Ri|≤d = _i|R_i|≤ d and E E is in D; moreover, by Claim D.1, E E is admissible for ℛR and at swap distance exactly d′d from E. Otherwise, f(ℛ)=d′f(R)=d is the finite value returned by some branch with state ℛ′R , where ℛ′R arises from ℛR by adding one pair to some RiR_i. By the induction hypothesis, we get that d′≤d ≤ d and there is an election in D admissible for ℛ′R at swap distance exactly d′d from E; since Ri⊆Ri′R_i R _i for every i, every election admissible for ℛ′R is admissible for ℛR, which completes the proof. ∎ Claim D.3. If there is an election E′E in D admissible for ℛR at swap distance d′≤d ≤ d from E, then the algorithms set f(ℛ)f(R) to a value at most d′d . Proof. We proceed by induction over d′−∑i|Ri|d - _i|R_i|, and denote the votes of E′E by v1′,…,vn′v _1,…,v _n. Since E′E is admissible for ℛR, we have ∑i|Ri|≤∑idist(vi,vi′)=d′≤d _i|R_i|≤ _idist(v_i,v _i)=d ≤ d, so the algorithm does not set f(ℛ)f(R) as ∞ in the initial pruning step. Suppose first that some TiT_i contains a directed triangle. No linear order realizes all three arcs of a directed triangle, and vi′v _i realizes all arcs of RiR_i; hence vi′v _i inverts, relative to viv_i, at least one pair of the triangle outside RiR_i. In particular, not all three arcs belong to RiR_i, and E′E is admissible for the state ℛ′R of the corresponding branch. By the induction hypothesis, the algorithm computes a value f(ℛ′)≤df(R )≤ d in that branch, which implies f(ℛ)≤f(ℛ′)≤df(R)≤ f(R )≤ d. Suppose next that all tournaments are acyclic. If the algorithm finds that E E belongs to D, then it returns the value ∑i|Ri|≤d _i|R_i|≤ d. Otherwise, assume that it finds a forbidden partial subelection (C⋆,V⋆)∈ℱ(C ,V ) present in E E; let π:C⋆→Cπ:C → C and φ:V⋆→V :V → V be the injections witnessing this. Since E′∈E , we know that (C⋆,V⋆)(C ,V ) is not present in E′E . Consequently, there exists some v∈V⋆v∈ V and a pair (a,b)∈Pv(a,b)∈ P_v for which the voter φ(v)=v^i (v)= v_i in E E and the corresponding voter vi′v _i in E′E ranks π(a)π(a) and π(b)π(b) differently. By Claim D.1, vi′v _i agrees with v^i v_i on all pairs in RiR_i, so π(a),π(b)∉Ri\π(a),π(b)\∉ R_i, and v^i v_i orders π(a),π(b)\π(a),π(b)\ as viv_i does. Hence, vi′v _i inverts π(a),π(b)\π(a),π(b)\ relative to viv_i and so E′E is admissible for the state of the branch that adds π(a),π(b)\π(a),π(b)\ to RiR_i. By the induction hypothesis, this branch returns a value at most d′d , which ensures that the algorithm sets f(ℛ)f(R) to a value at most d′d . ∎ Combining Claims D.2 and D.3, the algorithm sets f(ℛ)f(R) as the minimum swap distance between E and an election in D admissible for ℛR if this distance is at most d, and ∞ otherwise. In particular, f(ℛ0)f(R_0) is a finite value if and only if some election in D lies within swap distance d of E, and in that case it returns the minimum such distance. D.2 An alternative algorithm for Nearly GS Election Theorem D.4. Nearly GSGS Election can be solved in ∗(23d2+(dlogd))O^*(2^3d^2+O(d d)) time. Proof. Let E=(C,V)E=(C,V) be our input election, and d our budget. We say that (C1,C2)(C_1,C_2) is a clean split for E if in each vote v∈Vv∈ V, either all candidates in C1C_1 precede all those in C2C_2, or vice versa, all candidates in C2C_2 precede those in C1C_1. We start with a claim that allows us to divide an instance into two smaller instances whenever the election admits a clean split. Claim D.5. Suppose that (C1,C2)(C_1,C_2) is a partition of C into two non-empty sets that is a clean split for E. Let d0=dist(E,GS)d_0=dist(E,GS), d1=dist(E↾C1,GS)d_1=dist(E_ _C_1,GS), and d2=dist(E↾C2,GS)d_2=dist(E_ _C_2,GS) be the swap distances of E, of E↾C1E_ _C_1, and of E↾C2E_ _C_2, respectively, from the family of GSGS domains. Then d0=d1+d2d_0=d_1+d_2. Proof. For two votes u and w over the same candidate set, let Inv(u,w)Inv(u,w) denote the set of candidate pairs that are ordered differently in u and in w; recall that dist(u,w)=|Inv(u,w)|dist(u,w)=|Inv(u,w)|. We use the following two observations. First, for each subset D of candidates, Inv(u↾D,w↾D)=Inv(u,w)∩(D2),Inv(u_ _D,w_ _D)=Inv(u,w)∩ D2, (10) since restricting both votes to D retains exactly those pairs having both of their candidates in D. Second, given a binary QQ-tree T with a mapping φ and a subset D of candidates, let T↾DT_ _D denote the binary QQ-tree obtained from T by deleting all leaves in φ(C∖D) (C D) and then contracting every edge that connects a node to a unique child. Then u↾D∈(T↾D,φ↾D) for each vote u∈(T,φ),u_ _D (T_ _D, _ _D) for each vote u (T, ), (11) because the permutations of the children of the internal nodes of T that witness u∈(T,φ)u (T, ) induce such permutations in T↾DT_ _D as well. We first prove d1+d2≤d0d_1+d_2≤ d_0; note that this direction holds for an arbitrary partition (C1,C2)(C_1,C_2) of C. Let T be a binary QQ-tree with a mapping φ such that dist(E,(T,φ))=d0dist(E,D(T, ))=d_0, and for each vote v of E let uvu_v be a vote in (T,φ)D(T, ) closest to v. Since the pairs within C1C_1 and the pairs within C2C_2 form two disjoint subsets of Inv(v,uv)Inv(v,u_v), we obtain from (10) that dist(v,uv)≥dist(v↾C1,uv↾C1)+dist(v↾C2,uv↾C2).dist(v,u_v) (v_ _C_1,u_v_ _C_1)+dist(v_ _C_2,u_v_ _C_2). By (11) we know uv↾Ci∈(T↾Ci,φ↾Ci)u_v_ _C_i (T_ _C_i, _ _C_i) for both i∈[2]i∈[2], so summing the above inequality over all votes of E yields d0=dist(E,(T,φ))≥∑i∈[2]dist(E↾Ci,(T↾Ci,φ↾Ci))≥d1+d2,d_0=dist(E,D(T, ))\\ ≥ _i∈[2]dist(E_ _C_i,D(T_ _C_i, _ _C_i))≥ d_1+d_2, where the last inequality holds because did_i is the smallest distance of E↾CiE_ _C_i from a GSGS domain. We now prove d0≤d1+d2d_0≤ d_1+d_2; this is the direction where we use that (C1,C2)(C_1,C_2) is a clean split. For each i∈[2]i∈[2], let TiT_i be a binary QQ-tree with a mapping φi _i from CiC_i to the leaves of TiT_i such that dist(E↾Ci,(Ti,φi))=didist(E_ _C_i,D(T_i, _i))=d_i. Let T be the binary QQ-tree whose root has T1T_1 and T2T_2 as the subtrees rooted at its two children, and let φ=φ1∪φ2 = _1∪ _2. Observe that a vote u belongs to (T,φ)D(T, ) whenever the candidates of C1C_1 and those of C2C_2 form two contiguous blocks in u and u↾Ci∈(Ti,φi)u_ _C_i (T_i, _i) for both i∈[2]i∈[2], since the permutation of the children of the root of T allows for both orders of these two blocks. Consider now a vote v of E, and for both i∈[2]i∈[2] let uiu_i be a vote in (Ti,φi)D(T_i, _i) closest to v↾Civ_ _C_i. As (C1,C2)(C_1,C_2) is a clean split, v is the concatenation of the blocks v↾C1v_ _C_1 and v↾C2v_ _C_2 in one of the two possible orders; let u be the concatenation of u1u_1 and u2u_2 in the same order. By the observation above, u∈(T,φ)u (T, ). Moreover, v and u order each pair of candidates coming from different sets C1C_1 and C2C_2 in the same way, so (10) yields dist(v,u)=dist(v↾C1,u1)+dist(v↾C2,u2).dist(v,u)=dist(v_ _C_1,u_1)+dist(v_ _C_2,u_2). Summing over all votes of E, we get d0≤dist(E,(T,φ))≤d1+d2,d_0 (E,D(T, ))≤ d_1+d_2, which finishes the proof. ∎ Our algorithm starts by trying to identify a clean split for E. To this end, we fix a vote v∈Vv∈ V, and we check for each k∈[m−1]k∈[m-1] whether the candidates ranked within the top k positions in v form a clean split (with the set of the remaining candidates) for E; this can be checked in time (m⋅n)O (m· n ). If so, we divide our instance along this split into two sub-instances using Claim D.5, and apply recursion. Henceforth, we assume that E admits no clean split. Consider now an election E′E in some GSGS domain with minimum swap distance from E, and let T be a binary QQ-tree with a mapping φ from C to the leaves of T such that E′∈(T,φ)E (T, ). Let us fix a vote v∈Vv∈ V and a default ordering of the leaves of T (complying with the structure of T) which results in a vote v′v in E′E closest to v among all votes in (T,φ)D(T, ). Let S⋆S denote the set of candidates mapped to leaves in the subtree of T rooted at the left child of the root r. We provide an algorithm that determines a family S of candidate sets in FPT time with parameter d such that S⋆∈S and |||S| is bounded by a function of d. First note that for a set S⊆CS C, we can compute in (m⋅n)O (m· n ) time the number of swaps necessary to ensure that (S,C∖S)(S,C S) becomes a clean split in E (i.e., so that in all votes of E, candidates in S are placed on the first or the last |S||S| positions); we call this the cost of the split induced by S and denote it as cost(S)cost(S). Given a position k∈[m−1]k∈[m-1], we call a candidate set S valid for k if |S|=k|S|=k, cost(S)≤dcost(S)≤ d, and at most d swaps suffice to move S to the first positions in v. Clearly, S⋆S is valid for |S⋆||S |. Claim D.6. For a fixed k∈[m−1]k∈[m-1], there are at most 22d2^2d candidate sets valid for k. All such sets and their costs can be computed in ∗(22d)O^*(2^2d) time. Proof. Let Cjv=c:c∈C,posv(c)≤jC^v_j=\c c∈ C,pos_v(c)≤ j\ for each j∈[m]j∈[m]. If S is valid for k, then we can move all candidates in S with at most d swaps to the first k positions in v. This implies Ck−dv⊆SC_k-d^v S and S∩(C∖Ck+dv)=∅S∩(C C^v_k+d)= , yielding at most 22d2^2d possibilities for S. To compute cost(S)cost(S), we simply need to calculate the number of swaps in each vote that suffices to move S to the first or the last k positions; this can be done in (m⋅n)O (m· n ) time. ∎ We say that a position in [m−1][m-1] is valid if there exists a candidate set that is valid for it. Claim D.7. If E admits no clean split, then there are at most 8d⋅2d8d· 2^d valid positions. Proof. Let d′=2d =2d. Fix some valid position k∈[m−1]k∈[m-1], and consider the path PkP_k in T leading from the root to the k-th leaf κ (counted from the left). We say that a node x on this path is heavy, if the subtree rooted at x has more than 2d′2d leaves to the left of κ and more than 2d′2d leaves to the right of κ. By definition, if a node of PkP_k is heavy, then so is its parent. Let Pk′P _k denote the subpath of PkP_k formed by heavy nodes. We say that a node x and its child y, both on Pk′P _k, form a rigid pair if for each vote v v of E′E , the children of x have to be reversed (compared to their ordering in T) if and only if the children of y have to be reversed when constructing the vote v^∈(T,φ) v (T, ). We claim that all edges on Pk′P _k form a rigid pair. Assume for a contradiction that (x,y)(x,y) is not rigid for some edge x,y\x,y\ on Pk′P _k; we choose x to be as close to the root as possible. Let the subpath of Pk′P _k between x and the root r be denoted by PrxP_rx. Let T1,T2,…,TℓT_1,T_2,…,T_ denote the trees obtained from T by deleting the vertices of PrxP_rx, where ℓ−1 -1 is the number of vertices on PrxP_rx, and let TiT_i be the unique tree among these that contains y. For each j∈[ℓ]j∈[ ], let AjA_j denote the candidates mapped by φ to the leaves of TjT_j, and we assume that the default ordering of T yields a left-to-right order of the candidates that is a refinement of A1,A2,…,AℓA_1,A_2,…,A_ ; we call this series the partitioning of C induced by the path PrxP_rx. By our choice of x, all edges on PrxP_rx are rigid. Therefore, in all votes v v in E′E , the ordering of the candidates is a refinement of either A1,A2,…,AℓA_1,A_2,…,A_ or of Aℓ,Aℓ−1,…,A1A_ ,A_ -1,…,A_1. Let S be a candidate set valid for k. By definition, it is possible to move S to the first k positions in v by at most d swaps. Moreover, v′v can also be obtained from v by at most d swaps. Therefore, it is possible to move S to the first k positions in v′v using at most d′=2d =2d swaps; we refer to this fact as (⧫ ). Since y is heavy, this implies that A1∪⋯∪Ai−1⊆SA_1∪·s∪ A_i-1 S and (Ai+1∪⋯∪Aℓ)∩S=∅(A_i+1∪·s∪ A_ )∩ S= ; we refer by (♠ ) to this property. Let Ti1T_i^1 and Ti2T_i^2 denote the subtrees rooted at the left and right child of y (according to the default ordering of T), with candidates sets Ai1A_i^1 and Ai2A_i^2 mapped to their leaves, respectively. Since (x,y)(x,y) is not rigid, there exists a vote v v in E′E where the ordering of the candidates is a refinement of A1,…,Ai−1,Ai2,Ai1,Ai+1,…,AℓA_1,…,A_i-1,A^2_i,A^1_i,A_i+1,…,A_ or its reverse; we assume the former, as the latter case is analogous. Due to (♠ ) and |Ai|>4d′|A_i|>4d , it is not possible to move the vertices in S to the last k positions in v′v with at most d′d swaps; thus, we need to move S to the first k positions in v′v . Since S is valid for k and y is heavy, we have that • the set B1⊆Ai1B_1 A_i^1 of candidates with rank at most k−d′k-d in v′v must be in S, and • the set B2⊆Ai2B_2 A_i^2 of candidates with rank at least k+d′+1k+d +1 in v′v is disjoint from S. First, if κ is contained in Ti2T_i^2, then by |Ai1∖B1|≤d′−1|A_i^1 B_1|≤ d -1 we know that at least one candidate from B1B_1, say b1b_1, must have rank at least k+d′+1k+d +1 in v v. This means that b1b_1 cannot be moved to the first k positions within v v using at most d′d swaps. However, by b1∈Sb_1∈ S, this contradicts (⧫ ). Second, if κ is contained in Ti1T_i^1, then by |Ai2∖B2|≤d′|A_i^2 B_2|≤ d , at least one candidate from B2B_2, say b2b_2, must have rank at most k−d′k-d in v v; however, this means that b2b_2 cannot be moved out from the first k positions within v v with at most d′d swaps. By b2∉Sb_2∉ S, this again contradicts (⧫ ). This proves that each edge on Pk′P _k forms a rigid pair. Let A1,…,Aℓ′A_1,…,A_ denote the partitioning of C induced by Pk′P _k. Since all edges on Pk′P _k are rigid, in all votes v v in E′E , the ordering of the candidates is a refinement of either A1,…,Aℓ′A_1,…,A_ or of Aℓ′,…,A1A_ ,…,A_1. Thus, (A1∪⋯∪Ai,Ai+1∪⋯∪Aℓ′)(A_1∪·s∪ A_i,A_i+1∪·s∪ A_ ) forms a clean split for each i∈[ℓ′−1]i∈[ -1] for E′E . However, since E has swap distance at most d from E′E , and by applying d swaps one can increase the cost of at most d of these splits, we obtain that ℓ′−1≤d -1≤ d, as otherwise E would admit at least one clean split, a contradiction. This implies that the node on Pk′P _k farthest from r is at most d edges away from r within T; we call this node the guard for k, and denote it as g(k)g(k). Let z be the non-heavy child of g(k)g(k) that contains κ. Since z is not heavy, we know that κ is among the first or last 2d′=4d2d =4d leaves within the subtree of T rooted g(k)g(k). Therefore, for each node t in T, there can be at most 8d8d valid positions whose guard is t. Moreover, t can only be a guard if it is at most d edges away from the root, implying that there are most 2d2^d guards. Thus, there are at most 8d⋅2d8d· 2^d valid positions in total. ∎ Claims D.6 and D.7 offer a straightforward approach to construct the desired family S of candidate sets: for each position k, we compute the set of all valid candidate sets. By Claim D.6, this can be done in ∗(22d)O^*(2^2d) time and by Claim D.6, the size of the resulting family S is in ∗(8d⋅23d)O^*(8d· 2^3d). Therefore, we can use a classic bounded-search tree approach: if E admits no clean split, we branch by guessing the set S⋆S from among all sets in S, and in each branch separate our instance to two sub-instances restricted to S⋆S and to C∖S⋆C S . We solve the two obtained sub-instances recursively; note that the parameter decreases by cost(S⋆)>0cost(S )>0 in both sub-instances. The recursion stops trivially on instances with only one candidate or with a negative budget. Since the height of the resulting search tree is at most d, the total running time is ∗((8d⋅23d)d)=∗(23d2+(dlogd))O^* ((8d· 2^3d)^d )=O^*(2^3d^2+O(d d)). ∎ D.3 Proof of Theorem 4.9 See 4.9 We prove the two results separately, in Theorems D.8 and D.9. We start with our algorithm for Nearly GS/catGS/ Election, which uses a simpler branching strategy than our algorithm for Nearly GS/catGS/ Election, thanks to the following fact: if x is an inner node of a caterpillar tree and CxC_x denotes the set of candidates mapped to the leaves of the subtree rooted at x, then the corresponding partitioning of CxC_x (formed by the candidate sets mapped to the leaves of the subtree rooted at the left and the right child of x) always consists of a singleton c\c\ and the remainder Cx∖cC_x \c\ for some candidate c∈Cxc∈ C_x. Theorem D.8. Nearly GS/catGS/ Election can be solved in 2(d⋅logd)⋅(mn)(1)2^O (d· d )·(mn)^O (1 ) time. Proof. The algorithm is a bounded-search-tree exploration of the search space. We start with an election E=(C,V)E=(C,V) and the caterpillar QQ-tree T with m leaves ℓ1,…,ℓm _1,…, _m, with the mapping of the candidate set to the leaves not yet fixed. In every step, we fix the candidate mapped to at least one leaf; every branching step additionally decreases the remaining budget by at least one. The algorithm relies on the two following observations: (i) If a candidate c is ranked first or last by every voter, then some optimal solution places c on the left-most leaf, and we may fix it there and remove it from the instance. (i) Given an election (C′,V)(C ,V), we can check in polynomial time whether it is caterpillar-consistent. The property in (i) can also be verified in polynomial time; we call a candidate c satisfying it an ideal candidate. To prove (i), let c be an ideal candidate and let E′E be a caterpillar-consistent election that can be obtained from E using d swaps. We construct a caterpillar-consistent election E′E that can be obtained from E using at most d swaps and whose mapping places c on the left-most leaf. In each vote of E′E , we place c at the extreme position (first or last) that it occupies in the corresponding vote of E, and we order the remaining candidates as in the corresponding vote of E′E . Since the swap distance of two votes is the number of candidate pairs they order differently, and since each vote of E′E agrees with the corresponding vote of E on every pair containing c and with the corresponding vote of E′E on every other pair, the election E′E can indeed be obtained from E using at most d swaps. Moreover, E′E is caterpillar-consistent: as the GS/catGS/ domain is hereditary (Kraiczy and Elkind 2022), the election E′↾C∖c=E′↾C∖cE _ _C \c\=E _ _C \c\ is caterpillar-consistent with respect to some mapping φ′ , and since every vote of E′E ranks c first or last, by the recursive characterization E′E is caterpillar-consistent with respect to the mapping that places c on the left-most leaf, followed by φ′ . Hence some optimal solution places c on the left-most leaf and never swaps c. Applying this construction to an optimal E′E further shows that the optimal number of swaps for E equals that for E↾C∖cE_ _C \c\: the solution E′E restricted to C∖cC \c\ costs the same number of swaps, and conversely, re-inserting c at its original extreme positions into any caterpillar-consistent election obtained from E↾C∖cE_ _C \c\ costs no additional swaps and, by the argument above, preserves caterpillar-consistency. We may therefore fix c on the left-most leaf and remove it from the instance. A state of the algorithm is a pair (C′,d′)(C ,d ), where C′⊆CC C and d′≤d ≤ d is the remaining number of swaps. Each state returns the minimum number of swaps necessary to make the election E↾C′E_ _C caterpillar-consistent if this number is at most d′d , and ∞ otherwise. The whole instance is a yes-instance if and only if the initial state (C,d)(C,d) returns a finite value. Assume the algorithm is in a state (C′,d′)(C ,d ). If E↾C′E_ _C is caterpillar-consistent, we return 00, as no swap is necessary. Otherwise, as long as C′C contains an ideal candidate, we fix it on the left-most free leaf and remove it from C′C , which by (i) preserves optimality and costs no swaps. After all ideal candidates have been removed, every remaining candidate requires at least one swap to become ideal. We now create the branching states. We fix a single voter v1v_1 and let P⊆C′P C be the set of candidates that v1v_1 ranks among its top d′+1d +1 or bottom d′+1d +1 positions; then |P|≤2d′+2|P|≤ 2d +2. No other candidate can occupy the left-most leaf of a caterpillar tree representing an election that has swap distance at most d′d from E↾C′E_ _C : such a candidate would have to become first or last in v1v_1, which alone would already require more than d′d swaps, as more than d′d candidates separate it from either end of v1v_1. For each candidate c∈Pc∈ P we compute the number σc _c of swaps required to make c ideal, i.e., σc=∑v∈Vminposv↾C′(c)−1,|C′|−posv↾C′(c) _c= _v∈ V \pos_v_ _C (c)-1,\ |C |-pos_v_ _C (c)\, moving c to its cheaper extreme in each vote independently; we discard c if σc>d′ _c>d , and let P′=c∈P:σc≤d′P =\c∈ P: _c≤ d \. If P′=∅P = , we return ∞: in any caterpillar-consistent election within swap distance d′d of E↾C′E_ _C , the candidate c on the left-most leaf is first or last in every vote, so already the swaps of pairs containing c certify σc≤d′ _c≤ d ; hence no caterpillar election lies within swap distance d′d of this sub-election. Otherwise we branch over the candidates c∈P′c∈ P : for each, we make c ideal at cost σc _c, fix it on the left-most leaf, and recurse on (C′∖c,d′−σc)(C \c\,d - _c); note that the swaps making c ideal only affect pairs containing c, so the remaining sub-election is again the restriction E↾C′∖cE_ _C \c\ of the original election. We return the minimum over c∈P′c∈ P of σc _c plus the value returned from the corresponding subproblem. This is correct since the swap distance decomposes over candidate pairs: any solution placing c on the left-most leaf spends at least σc _c swaps on pairs containing c and at least the optimum of E↾C′∖cE_ _C \c\ on the remaining pairs, and conversely, combining the σc _c swaps with an optimal solution for E↾C′∖cE_ _C \c\ yields a caterpillar-consistent election, as in (i). There are at most 2d′+22d +2 branches in each state, and each recursive call decreases d′d by at least one, as every candidate in P′P requires at least one swap to become ideal. Hence, starting from (C,d)(C,d), we obtain a search tree of size (2d+2)d=d(d)(2d+2)^d=d^O (d ), and in each state we spend (mn)(1)(mn)^O (1 ) time for the checks of (i) and (i) and for computing the values σc _c. Therefore the algorithm runs in 2(d⋅logd)⋅(mn)(1)2^O (d· d )·(mn)^O (1 ) time.∎ Next, we apply the same technique to solve Nearly GS/balGS/ Election; the branching step here will be more involved. Theorem D.9. Nearly GS/balGS/ Election can be solved in 2(d2)⋅(mn)(1)2^O (d^2 )·(mn)^O (1 ) time. Proof. The algorithm uses a bounded-search-tree strategy. Let E=(C,V)E=(C,V) and d be our input, and recall that for an election to belong to GS/balGS/ we need m=|C|=2tm=|C|=2^t for some integer t; otherwise we reject immediately. Throughout, C′C denotes a subset of C whose size is a power of 22, and we write opt(C′)=dist(E↾C′,GS/bal)opt(C )=dist(E_ _C ,GS/ ). We call a partitioning (L,R)(L,R) of C′C with |L|=|R|=|C′|/2|L|=|R|= |C |2 a split of C′C , and we let sc(L,R)sc(L,R) denote the number of swaps needed to ensure that each voter ranks either all of L above all of R, or vice versa; that is, sc(L,R)=∑v∈Vminxv,|L|⋅|R|−xv,sc(L,R)= _v∈ V \x_v,\ |L|·|R|-x_v\, where xv=|(l,r)∈L×R:r≻vl|x_v=|\(l,r)∈ L× R r _vl\|. A split with sc(L,R)=0sc(L,R)=0 is a clean split for E↾C′E_ _C . Note that sc(L,R)sc(L,R) is computable in (mn)O (mn ) time. Two observations. We first record the recursion underlying the algorithm. Claim D.10. For each C′C with |C′|≥2|C |≥ 2 we have opt(C′)=min(L,R)(sc(L,R)+opt(L)+opt(R))opt(C )= _(L,R) (sc(L,R)+opt(L)+opt(R) ), where the minimum is taken over all splits (L,R)(L,R) of C′C . Proof. Let T be a balanced QQ-tree with a mapping φ from C′C to its leaves, and let (L,R)(L,R) be the sets of candidates mapped to the leaves of the two subtrees rooted at the children of the root of T. Every vote of (T,φ)D(T, ) ranks the candidates of L and those of R in two contiguous blocks, in one of the two possible orders, and its restrictions to L and to R range independently over the domains defined by the two subtrees. Since the swap distance of two votes is the number of candidate pairs they order differently, and since each candidate pair either belongs to L×RL× R or lies within L or within R, we get dist(E↾C′,(T,φ))=sc(L,R)+dist(E↾L,(TL,φ↾L))+dist(E↾R,(TR,φ↾R))dist(E_ _C ,D(T, ))=sc(L,R)+dist(E_ _L,D(T^L, _ _L))+dist(E_ _R,D(T^R, _ _R)) for the two subtrees TLT^L and TRT^R. Taking the minimum over all balanced QQ-trees and mappings, and noting that each split (L,R)(L,R) of C′C arises from some such tree, proves the claim. ∎ Claim D.11. The election E↾C′E_ _C has at most one clean split, and it can be identified in (mn)O (mn ) time. Proof. Let (L,R)(L,R) be a clean split for E↾C′E_ _C and let v be any vote of V. Then L consists of the candidates that v ranks within the top |C′|/2 |C |2 positions of C′C , or of those it ranks within the bottom |C′|/2 |C |2 positions; thus L,R\L,R\ is determined by v. To find it, we compute this partitioning for one fixed vote and check in (mn)O (mn ) time whether it is clean. ∎ The skeleton. By Claim D.11 we may define, for each C′C , the following rooted tree, the skeleton of E↾C′E_ _C : its root is C′C ; a node D with |D|≥2|D|≥ 2 is a leaf and is called blocked if E↾DE_ _D has no clean split, and otherwise its two children are the two sides of the unique clean split of E↾DE_ _D; nodes of size 11 are leaves as well. Observe that the blocked nodes are pairwise disjoint, and that the skeleton has depth at most logm m. We call a node of the skeleton active if the subtree of the skeleton rooted at it contains a blocked node; the active nodes are thus exactly the ancestors of blocked nodes, including the blocked nodes themselves. Since each blocked node has at most logm+1 m+1 ancestors, including itself, a skeleton with b blocked nodes has at most b(logm+1)b\,( m+1) active nodes. Note also that if the skeleton of E↾DE_ _D contains no blocked node, then it is a perfect binary tree whose leaves are the singletons of D; regarding it as a balanced QQ-tree T and letting φ map each candidate to its own leaf, every vote of E↾DE_ _D lies in (T,φ)D(T, ) by the definition of a clean split, and hence opt(D)=0opt(D)=0. Few blocked nodes. The following lemma is the heart of the running-time analysis: it states that a bounded budget permits only a bounded number of blocked nodes, no matter how large m is. Claim D.12. The skeleton of E↾C′E_ _C contains at most 2opt(C′)2\,opt(C ) blocked nodes. Proof. It suffices to prove the statement for C′=C =C: the general case follows by applying it to the election E↾C′E_ _C in place of E. We may further assume V≠∅V≠ , as otherwise every split is clean and no node is blocked. Let F be an election in a GS/balGS/ domain (T,φ)D(T, ) with dist(E,F)=opt(C)dist(E,F)=opt(C), and for each vote v of E let vFv^F be the corresponding vote of F. We say that a candidate pair touches a set D if at least one of its two candidates lies in D, and we call it broken if some vote v of E orders it differently than vFv^F does. The number of broken pairs is at most dist(E,F)=opt(C)dist(E,F)=opt(C). We show that every blocked node D is touched by a broken pair; since the blocked nodes are pairwise disjoint and each pair touches at most two of them, this proves the claim. We first observe that in each vote v of E, the candidates of a skeleton node D with |D|=2j|D|=2^j occupy the positions a2j+1,a2j+2,…,(a+1)2ja2^j+1,a2^j+2,…,(a+1)2^j for some integer a≥0a≥ 0; we call such a set of positions a block. This holds for the root C, and if it holds for a node, then its two children each occupy the upper or the lower half of its block, which is again a block. Now suppose for contradiction that no broken pair touches the blocked node D, that is, v and vFv^F order every pair touching D in the same way, for every vote v. Then each candidate of D is preceded by the same candidates in v as in vFv^F, so the candidates of D occupy the same positions in v and in vFv^F, and E↾DE_ _D and F↾DF_ _D are the same election. By the previous paragraph, the candidates of D therefore occupy a block in each vote of F. Next, we claim that in any vote u∈(T,φ)u (T, ), the candidates occupying a block of size 2j2^j are exactly those mapped by φ to the leaves of the subtree rooted at some node of T at distance t−jt-j from its root. Indeed, a vote of (T,φ)D(T, ) arises by permuting the children of the nodes of T and reading the leaves from left to right; as T is a perfect binary tree, the leaves of the subtrees rooted at the nodes at distance t−jt-j from the root occupy consecutive blocks of size 2j2^j in this reading, in some order. Since the candidate sets belonging to the nodes of T at a fixed distance from the root are pairwise disjoint, and D coincides with one of them, as witnessed by any single vote of F, the set D is the candidate set of a single node t⋆t of T. Consequently F↾DF_ _D lies in the domain defined by the subtree of T rooted at t⋆t , which is a perfect binary QQ-tree; in particular, the two candidate sets belonging to the children of t⋆t form a clean split for F↾D=E↾DF_ _D=E_ _D, contradicting the assumption that D is blocked. ∎ The algorithm. A state is a pair (C′,d′)(C ,d ) with d′≤d ≤ d; it returns minopt(C′),d′+1 \opt(C ),d +1\, so that the input is a yes-instance if and only if the initial state (C,d)(C,d) returns a value of at most d. We proceed as follows on a state (C′,d′)(C ,d ). 1. If |C′|=1|C |=1, we return 00. 2. We build the skeleton of E↾C′E_ _C ; by Claim D.11 this takes polynomial time. If it contains no blocked node, then opt(C′)=0opt(C )=0 as observed above, and we return 00. If it contains more than 2d′2d blocked nodes, then opt(C′)>d′opt(C )>d by Claim D.12 and we return d′+1d +1. 3. Otherwise, we fix a vote v∈Vv∈ V and let P contain those candidates of C′C that v↾C′v_ _C ranks within d′d positions of the boundary between the top and the bottom half of C′C ; thus |P|≤2d′|P|≤ 2d . Any candidate of C′∖PC P lies more than d′d positions away from this boundary, so moving it to the other half would already require more than d′d swaps within v; hence every split (L,R)(L,R) with sc(L,R)≤d′sc(L,R)≤ d agrees with the split of v↾C′v_ _C into its top and bottom half outside of P. We branch over all at most (2d′d′)<4d′ 2d d <4^d splits of this form. For each of them we compute sc(L,R)sc(L,R), discard it if sc(L,R)>d′sc(L,R)>d , and otherwise recurse on the states (L,d′−sc(L,R))(L,d -sc(L,R)) and (R,d′−sc(L,R))(R,d -sc(L,R)). We return the minimum of sc(L,R)+αL+αRsc(L,R)+ _L+ _R over the surviving splits (i.e., over those splits in which both calls return a value at most d′−sc(L,R)d -sc(L,R)), where αL _L and αR _R are the values returned by the two recursive calls, capped at d′+1d +1. Correctness is immediate from Claim D.10 together with the observation in step 3 that all splits of cost at most d′d are among those we enumerate: the optimum of the recursion in Claim D.10 is attained either by such a split, or opt(C′)>d′opt(C )>d and the returned value exceeds d′d as well. Running time. Consider the search tree T of the algorithm in which every node x is a call of the algorithm, initiated with some state of the algorithm. We call an edge of T free if it corresponds to a split of cost 00, and paying otherwise. By Claim D.11, a state has at most one clean split available, so the free edges leaving a node x of T lead to the two sides of the unique clean split of the state corresponding to x. Consequently, the descendants of a node x with state (C′,d′)(C ,d ) that are reachable from x using free edges only form a subgraph of the skeleton of E↾C′E_ _C ; let xS_x denote this subgraph of T. Observe that each node of xS_x that is not a leaf in T must be an active node in xS_x, due to step 2. Again by step 2, the skeleton of a state (C′,d′)(C ,d ) corresponding to some non-leaf node of T contains at most 2d′2d blocked nodes and, hence, at most 2d′(logm+1)2d ( m+1) active nodes; therefore, the number of nodes in xS_x is at most 2d′(logm+1)2d ( m+1). For each node y in xS_x, the children of y outside xS_x arise as a consequence of at most 4d′4^d (non-clean) splits: each split yields two recursive calls, with the budget decreased by at least 11 in both. This means that each node y in xS_x has at most 2⋅4d′2· 4^d children in T but outside xS_x. Moreover, y is connected each these children nodes via a paying edge, each of them associated with a state having decreased parameter. Writing N(d′)N(d ) for the maximum number of non-leaf nodes in a search tree whose root has initial budget d′d , we thus get N(d′)≤2d′(logm+1)⋅(1+2⋅4d′N(d′−1)).N(d )≤ 2d ( m+1)· (1+2· 4^d N(d -1) ). Using induction on d, one can prove that this implies N(d)≤(4d(logm+1)4d)d=2(d2)⋅(logm)(d).N(d)≤ (4d( m+1)4^d )^d=2^O (d^2 )·( m)^O (d ). Finally, we show (logm)d≤2d2+mo(1)( m)^d≤ 2^d^2+m^o(1): if logm≤2d m≤ 2^d, then (logm)d≤2d2( m)^d≤ 2^d^2, and otherwise d<loglogmd< m and thus (logm)d<2(loglogm)2=mo(1)( m)^d<2^( m)^2=m^o(1). Since we spend polynomial time in each state, the total running time of the algorithm is 2(d2)⋅(mn)(1)2^O (d^2 )·(mn)^O (1 ). ∎ D.4 Proof of Theorem 4.10 See 4.10 We prove the results one by one in the following four theorems. Theorem D.13. Nearly k-Stratificationk- Election can be solved in 3d⋅(mn)3^d·O (mn ) time for any integer k. Proof. Let E=(C,V)E=(C,V) and d be our input instance with |C|=m|C|=m. Let T be the tree representing the k-Stratificationk- domain for m candidates, and let φ be a bijection from C to the leaves of T such that E has minimum swap distance from (T,φ)D(T, ). We start by computing the set C1C_1 of candidates that are mapped by φ to the children of the first PP-node in T. For a vote v∈Vv∈ V, let FvF_v denote the set of candidates appearing on the first m/km/k positions in v. We will call a candidate c dirty if c is in FvF_v for some but not all votes v. As long as there exists some dirty candidate c, we proceed as follows. First, we guess whether c∈C1c∈ C_1 or not, and find a vote v where c appears in the “wrong half” of v. That is, if c∈C1c∈ C_1, we find a vote v where c∉Fvc∉ F_v, and we guess the candidate b closest to c in v that precedes c but is not in C1C_1; such a candidate must exist by |C1|=|Fv||C_1|=|F_v|. In a correct guess, posv(c)−posv(b)≤dpos_v(c)-pos_v(b)≤ d, because b and c need to be swapped, which requires posv(c)−posv(b)pos_v(c)-pos_v(b) swaps (as b needs to be swapped with c and all candidates between b and c in v, all belonging to C1C_1). Similarly, if c∉C1c∉ C_1, then we find a vote v where c∈Fvc∈ F_v, and we guess the candidate b closest to c that follows c and is in C1C_1; again, swapping b and c requires posv(b)−posv(c)pos_v(b)-pos_v(c) swaps. In both cases, we perform the necessary dc=|posv(b)−posv(c)|d_c=|pos_v(b)-pos_v(c)| swaps, decrease the distance budget by dcd_c, and proceed with the next dirty candidate. If there are no dirty candidates left, it must be the case that C1=FvC_1=F_v for all votes v∈Vv∈ V. Hence, we remove C1C_1 from the set of candidates, and proceed with the remaining instance of Nearly (k−1)-Stratification(k-1)- Election. To compute the running time of this algorithm, let tm,n(d)t^m,n(d) denote the running time on an instance with m candidates, n voters, and parameter d. Recall that we first make a binary guess, then branch into at most d possibilities for candidate b, decreasing the parameter by i in the i-th branch, for i∈[d]i∈[d]. Therefore, we have tm,n(d)≤2(tm,n(d−1)+tm,n(d−2)+⋯+tm,n(0))t^m,n(d)≤ 2 (t^m,n(d-1)+t^m,n(d-2)+·s+t^m,n(0) ) where we also know tm,n(0)=(m⋅n)t^m,n(0)=O (m· n ). Using induction on d, we can show that tm,n(d)=3d⋅(m⋅n)t^m,n(d)=3^d·O (m· n ), because tm,n(d) t^m,n(d) ≤2(3d−1+3d−2+⋯+1)⋅(m⋅n) ≤ 2(3^d-1+3^d-2+·s+1)·O (m· n ) =(3d−1)⋅(m⋅n)≤3d⋅(m⋅n).∎ =(3^d-1)·O (m· n )≤ 3^d·O (m· n ). Corollary D.14. Nearly m/2-Stratificationm/2- Election can be solved in 2.832d⋅(mn)2.832^d·O (mn ) time. Proof. The same algorithm can be used as in Theorem D.13 for k=m/2k=m/2; however, observe that guessing the candidate b is a binary guess if c∈C1c∈ C_1, and a ternary guess if c∉C1c∉ C_1, using that |C1|=2|C_1|=2. Thus, we obtain the recurrence tm,n(d)≤2tm,n(d−1)+2tm,n(d−2)+tm,n(d−3)t^m,n(d)≤ 2t^m,n(d-1)+2t^m,n(d-2)+t^m,n(d-3) which yields tm,n(d)≤2.832d⋅(m⋅n)t^m,n(d)≤ 2.832^d·O (m· n ). ∎ Theorem D.15. Nearly SeparationSeparation Election can be solved in 5d⋅(mn)5^d·O (mn ) time. Proof. We apply the same ideas as in Theorem D.13, and we re-use the notation therein for k=2k=2, in particular, we let FvF_v denote the candidates in the first m/2m/2 positions of v. Let us say that a candidate pair (c,c′)(c,c ) is dirty if there exist votes v and v′v such that (i) c and c′c are in the same half of v, meaning that either c,c′⊆Fv\c,c \ F_v or c,c′∩Fv=∅\c,c \∩ F_v= , but (i) c and c′c are not in the same half of v′v . Then some candidate in c,c′\c,c \ needs to be moved to the “other half” either in v or in v′v ; we first guess this vote v^∈v,v′ v∈\v,v \. Next, we guess which candidate, c or c′c , is the one to be moved in v v; let c c be this candidate. From this point on, we proceed as in Theorem D.13, guessing the candidate b closest to c c in the appropriate direction from c c in v v that needs to be swapped with c c. After performing these swaps and reducing the parameter with |posv^(c^)−posv^(b)||pos_ v( c)-pos_ v(b)|, we proceed with the next dirty pair. Once there are no dirty pairs left, we know that the election belongs to the SeparationSeparation domain. The running time of this algorithm can be computed with the same techniques as in Theorem D.13, using that the running time function satisfies tm,n(d)≤4(tm,n(d−1)+tm,n(d−2)+⋯+tm,n(0))t^m,n(d)≤ 4 (t^m,n(d-1)+t^m,n(d-2)+·s+t^m,n(0) ) due to the two binary guesses we start with in each iteration; this leads to tm,n(d)=5d⋅(m⋅n)t^m,n(d)=5^d·O (m· n ). ∎ Theorem D.16. Nearly AntagonismAntagonism Election can be solved in 3.06d⋅(mn)3.06^d·O (mn ) time. Proof. Consider an input election E=(C,V)E=(C,V) and distance d with n=|V|n=|V|. Let T be the tree with |C||C| leaves representing the AntagonismAntagonism domain, and φ a bijection from C to the leaves of T such that E has minimum swap distance from (T,φ)D(T, ). First, if n>dn>d, then there must exist a vote v in which no swaps are needed, that is, for which v∈(T,φ)v (T, ). We guess such a vote v, which immediately determines (T,φ)D(T, ), allowing us to compute the swap distance of E from (T,φ)D(T, ) in polynomial time. If n≤dn≤ d, then we proceed as follows. For each vote v, let v′v denote the vote in (T,φ)D(T, ) with minimal swap distance to v. We guess for each vote v whether v′v is obtained by reversing the children of the root of T (a type QQ node), and if so, we reverse the vote v in E. Assuming correct guesses, the obtained election E E has distance at most d from the IdentityIdentity domain if and only if E has distance at most d from the AntagonismAntagonism domain. Thus, we can apply the algorithm by Betzler et al. (2009) for Kemeny Aggregation which runs in ∗(1.53d)O^*(1.53^d) time. The total running time is therefore 2n⋅∗(1.53d)≤2d⋅∗(1.53d)=∗(3.06d)2^n·O^*(1.53^d)≤ 2^d·O^*(1.53^d)=O^*(3.06^d). ∎ D.5 Identity and Antagonism are hereditary Proposition D.17. Both IdentityIdentity and AntagonismAntagonism are hereditary and admit a finite set of forbidden subelections. Proof. For IdentityIdentity, the forbidden subelection EidE_ id consists of two voters v and v′v and two candidates c and d with v:c≻dv c d and v′:d≻cv d c. If an election E contains two distinct votes, then these disagree on some pair of candidates, which means that EidE_ id is present in E; conversely, an election whose votes all coincide clearly avoids EidE_ id (meaning that EidE_ id is not present in such an election). For AntagonismAntagonism, we forbid three subelections A1A_1, A2A_2, A3A_3, each consisting of two voters v and v′v and three candidates c, d, and e, where in all three v:c≻d≻ev c d e, and A1 A_1 :v′:c≻e≻d \ v c e d A2 A_2 :v′:d≻c≻e \ v d c e A3 A_3 :v′:d≻e≻c \ v d e c Two votes that are equal or reversals of each other restrict, on every set of three candidates, to two orders that are again equal or reversals of each other; in each AiA_i the two orders are neither. Hence no profile in AntagonismAntagonism contains any of A1,A2,A3A_1,A_2,A_3. Conversely, assume that none of A1,A2,A_1,A_2, or A3A_3 is present in some election E; we show that E belongs to an AntagonismAntagonism domain. We use induction over the size m of the candidate set C; note that the cases m≤2m≤ 2 are trivial. Let m≥3m≥ 3, and assume that our claim holds for all elections over candidate sets of size m−1m-1. Let u=(c1,…,cm)u=(c_1,…,c_m) and u′u be two votes in E. Since the claim holds for E↾C′E_ _C for C′=C∖cmC =C \c_m\, we know that u↾C′∈(c1,…,cm−1),(cm−1,…,c1)u _ _C ∈\(c_1,…,c_m-1),(c_m-1,…,c_1)\. We distinguish between two cases: Case A: If u↾C′=(c1,…,cm−1)u _ _C =(c_1,…,c_m-1). In this case, u′u cannot rank cmc_m before c1c_1, since then A3A_3 would be isomorphic to the restriction of E to cm,c1,c2\c_m,c_1,c_2\. Moreover, u′u cannot rank cmc_m in between two candidates cic_i and ci+1c_i+1 for some i∈[m−2]i∈[m-2], because then A1A_1 would be isomorphic to the restriction of E to ci,cm,ci+1\c_i,c_m,c_i+1\. Thus, u′u must place cmc_m after cm−1c_m-1, and thus u′u coincides with u. Case B: If u↾C′=(cm−1,…,c1)u _ _C =(c_m-1,…,c_1). In this case, u′u cannot rank cmc_m after c1c_1, since then A2A_2 would be isomorphic to the restriction of E to c1,c2,cm\c_1,c_2,c_m\. Moreover, u′u cannot rank cmc_m in between two candidates cic_i and ci+1c_i+1 for some i∈[m−2]i∈[m-2], because then A3A_3 would be isomorphic to the restriction of E to ci,ci+1,cm\c_i,c_i+1,c_m\. Thus, u′u must place cmc_m before cm−1c_m-1, and thus u′u is the reverse of u. This finishes the proof of claim, implying that E indeed belongs to the AntagonismAntagonism domain. We remark that the given characterization is minimal in the sense that not forbidding some AiA_i, i∈[3]i∈[3], to be present in an election E allows E to be a domain that is not an AntagonismAntagonism domain, as witnessed by the election AiA_i itself. ∎ Appendix E Additional material for Section 5 E.1 Additional material for Section 5.1 In Figures 4, 5, 6, 7, 8, 9, 10, 11 and 12, we also provide the running time analysis for the remaining domains used later for the map of elections experiment. Each election consisted of 96 voters and m candidates (x-axis). The running time in seconds (y-axis) is on a log scale. Each solver had 15 minutes to compute the distance and was not run for higher values of m if it failed to finish in time for some m′<m <m. The results are comparable to the normalized Mallows culture. The only culture where the FPT(m) $FPT$(m) algorithm is slower than all other algorithms except for the naïve brute-force is the group-separable caterpillar elections. Figure 4: Running time of our algorithms on 1000 elections sampled from the SP/Conitzer culture. Figure 5: Running time of our algorithms on 1000 elections sampled from the SP/Walsh culture. Figure 6: Running time of our algorithms on 1000 elections sampled from the Single-Crossing culture. Figure 7: Running time of our algorithms on 1000 elections sampled from the GS/cat culture. Figure 8: Running time of our algorithms on 1000 elections sampled from the GS/bal culture. Figure 9: Running time of our algorithms on 1000 elections sampled from the Impartial culture. Figure 10: Running time of our algorithms on 1000 elections sampled from the URN-0.2 culture. Figure 11: Running time of our algorithms on 1000 elections sampled from the URN-0.5 culture. Figure 12: Running time of our algorithms on 1000 elections sampled from the EUC/uni culture. E.2 Additional material for Section 5.2 Table 2 shows the swap distance to the closest election of each group-separable domain for the elections of the map experiment. Table 3 then shows similar numerical results for our statistically more significant study with 10001000 samples per data point. Table 2: Swap distance to the closest election of each group-separable domain for the elections of the map experiment (88 candidates, 9696 voters, 1010 elections per culture). The top panel reports absolute distances, the bottom panel the same statistics normalized per voter (i.e., divided by n=96n=96). The share column gives the percentage of elections for which the domain is the closest of the three (ties split evenly; the general group-separable domain is only credited when strictly closer than both special cases). In every row the domain with the largest share is set in bold; cells are shaded proportionally to their value relative to the maximum of their statistic over all cells (shares relative to 100%100\%). GS/cat GS/bal GS Culture avg± med min max share avg± med min max share avg± med min max share Absolute distance NM-0.1 108.6± 4.7 109 99 115 0 80.3± 6.5 79.5 69 91 20 76.6± 4.9 75.5 69 85 80 NM-0.3 270.1± 14.0 274.5 245 284 0 270.2± 20.3 273 247 312 0 247.3± 18.2 248 218 275 100 NM-0.5 383.5± 21.4 384 358 415 80 448.5± 31.7 448 401 492 0 383.1± 21.4 382.5 358 415 20 NM-0.7 448.9± 16.6 447.5 421 475 100 578.3± 14.6 580 560 604 0 448.9± 16.6 447.5 421 475 0 NM-0.9 465.2± 8.3 464.5 454 477 100 634.6± 11.3 632.5 620 659 0 465.2± 8.3 464.5 454 477 0 IC 464.9± 14.8 468.5 438 481 100 637.5± 9.0 637.5 622 653 0 464.9± 14.8 468.5 438 481 0 URN-0.2 277.1± 27.5 268.5 251 329 40 416.3± 51.5 408 356 500 0 269± 30.7 268 220 321 60 URN-0.5 167.4± 64.6 169.5 79 273 50 325.1± 82.5 357.5 204 430 0 153.5± 59.5 156 66 223 50 SP/Walsh 232.9± 11.7 234 214 250 0 265.3± 18.7 268 220 286 0 212.1± 13.8 214 183 237 100 SP/Conitzer 186.2± 20.6 179.5 165 235 0 177.9± 19.0 174 157 211 0 162.5± 18.3 155.5 147 209 100 SC 275.2± 14.3 276.5 244 295 0 316.1± 27.5 314.5 260 357 0 242.4± 19.4 242 214 274 100 EUC-sphere 243.6± 70.0 255 134 315 10 259.3± 48.6 271.5 179 324 10 181.4± 38.4 174.5 124 243 80 GS/cat 0± 0 0 0 0 100 611.1± 24.3 615.5 549 637 0 0± 0 0 0 0 0 GS/bal 300.7± 13.7 303.5 277 321 0 0± 0 0 0 0 100 0± 0 0 0 0 0 Distance per voter NM-0.1 1.13± 0.05 1.14 1.03 1.20 0.84± 0.07 0.83 0.72 0.95 0.80± 0.05 0.79 0.72 0.89 NM-0.3 2.81± 0.15 2.86 2.55 2.96 2.81± 0.21 2.84 2.57 3.25 2.58± 0.19 2.58 2.27 2.86 NM-0.5 3.99± 0.22 4.00 3.73 4.32 4.67± 0.33 4.67 4.18 5.12 3.99± 0.22 3.98 3.73 4.32 NM-0.7 4.68± 0.17 4.66 4.39 4.95 6.02± 0.15 6.04 5.83 6.29 4.68± 0.17 4.66 4.39 4.95 NM-0.9 4.85± 0.09 4.84 4.73 4.97 6.61± 0.12 6.59 6.46 6.86 4.85± 0.09 4.84 4.73 4.97 IC 4.84± 0.15 4.88 4.56 5.01 6.64± 0.09 6.64 6.48 6.80 4.84± 0.15 4.88 4.56 5.01 URN-0.2 2.89± 0.29 2.80 2.61 3.43 4.34± 0.54 4.25 3.71 5.21 2.80± 0.32 2.79 2.29 3.34 URN-0.5 1.74± 0.67 1.77 0.82 2.84 3.39± 0.86 3.72 2.12 4.48 1.60± 0.62 1.62 0.69 2.32 SP/Walsh 2.43± 0.12 2.44 2.23 2.60 2.76± 0.19 2.79 2.29 2.98 2.21± 0.14 2.23 1.91 2.47 SP/Conitzer 1.94± 0.21 1.87 1.72 2.45 1.85± 0.20 1.81 1.64 2.20 1.69± 0.19 1.62 1.53 2.18 SC 2.87± 0.15 2.88 2.54 3.07 3.29± 0.29 3.28 2.71 3.72 2.52± 0.20 2.52 2.23 2.85 EUC-sphere 2.54± 0.73 2.66 1.40 3.28 2.70± 0.51 2.83 1.86 3.38 1.89± 0.40 1.82 1.29 2.53 GS/cat 0.00± 0.00 0.00 0.00 0.00 6.37± 0.25 6.41 5.72 6.64 0.00± 0.00 0.00 0.00 0.00 GS/bal 3.13± 0.14 3.16 2.89 3.34 0.00± 0.00 0.00 0.00 0.00 0.00± 0.00 0.00 0.00 0.00 Table 3: Swap distance to the closest election of each restricted domain (88 candidates, 9696 voters, 10001000 elections per culture). The top panel reports absolute distances, the bottom panel the same statistics normalized per voter (i.e., divided by n=96n=96). The share column gives the percentage of elections for which the domain is the closest of the four (ties split evenly; the general group-separable domain is only credited when strictly closer than both special cases). In every row the domain with the largest share is set in bold; cells are shaded proportionally to their value relative to the maximum of their statistic over all cells (shares relative to 100%100\%). GS/cat GS/bal GS SPeak Culture avg± med min max share avg± med min max share avg± med min max share avg± med min max share Absolute distance NM-0.1 101.2± 9.4 101 66 133 0 75.0± 9.9 75 44 112 0 70.9± 8.4 71 44 97 0 31.5± 6.7 31 13 55 100 NM-0.3 268.6± 15.1 268 222 313 0 260.2± 20.2 260 195 324 0 239.3± 17.1 239 190 293 0 179.6± 17.0 180 129 233 100 NM-0.5 383.2± 15.7 384 334 422 5.4 443.7± 24.7 443 354 519 0 381.7± 16.2 382 334 422 0.3 352.5± 22.9 352 272 436 94.3 NM-0.7 447.0± 12.3 448 401 481 99.3 582.3± 20.1 583 502 641 0 447.0± 12.3 448 398 481 0.6 513.5± 23.4 514 439 591 0.1 NM-0.9 462.2± 10.8 463 423 488 99.7 629.6± 11.5 631 565 656 0 462.2± 10.8 463 423 488 0.3 644.7± 19.0 646 580 703 0 IC 462.9± 11.0 464 419 491 100 630.3± 11.2 632 587 657 0 462.9± 11.0 464 419 491 0 671.9± 15.3 673 607 714 0 URN-0.2 281.3± 56.8 289 59 418 49.95 429.8± 71.5 441 111 567 0 273.8± 57.7 281 59 411 47.65 389.8± 82.4 399 67 597 2.4 URN-0.5 187.7± 75.6 192 12 360 31.45 320.9± 102.4 335.5 20 526 0 173.1± 74.0 173 8 346 60.1 251.3± 102.5 251 4 536 8.45 SP/Walsh 235.8± 12.9 236 182 276 0 268.3± 20.5 267 202 343 0 217.9± 13.5 218 178 262 0 0± 0 0 0 0 100 SP/Conitzer 184.6± 16.1 185 136 234 0 178.3± 22.2 178 119 265 0 160.1± 17.1 160 106 206 0 0± 0 0 0 0 100 SC 265.3± 34.6 267 148 348 1.3 325.7± 33.4 327.5 215 417 0 237.8± 27.0 240 142 298 5.7 156.2± 38.7 157 29 265 93 1D EUC-cube 131.0± 41.7 132 26 256 0 162.4± 43.7 164 32 305 0 93.4± 29.1 94 5 172 0 0± 0 0 0 0 100 2D EUC-cube 276.5± 39.3 278 154 376 7.95 354.1± 52.9 358 162 485 0.7 248.6± 38.2 250 125 343 57.9 269.5± 59.7 274 78 393 33.45 3D EUC-cube 328.5± 35.3 331 197 425 17.9 424.4± 45.4 427.5 273 545 0 312.1± 35.3 313 191 419 56.25 342.4± 55.9 346 153 502 25.85 4D EUC-cube 354.8± 31.9 357 251 430 33.25 465.2± 41.2 467.5 333 571 0 345.9± 32.1 347 249 428 47.2 387.6± 56.0 389 211 540 19.55 5D EUC-cube 372.4± 30.7 374 252 455 43.4 488.7± 36.7 492 354 578 0 366.5± 31.4 368 252 454 39.45 411.9± 56.1 414 217 557 17.15 GS/cat 0± 0 0 0 0 100 622.1± 16.6 625 563 661 0 0± 0 0 0 0 0 577.4± 25.6 578 499 649 0 GS/bal 299.5± 12.2 301 251 325 0 0± 0 0 0 0 100 0± 0 0 0 0 0 300.1± 12.4 301 252 326 0 Distance per voter NM-0.1 1.05± 0.10 1.05 0.69 1.39 0.78± 0.10 0.78 0.46 1.17 0.74± 0.09 0.74 0.46 1.01 0.33± 0.07 0.32 0.14 0.57 NM-0.3 2.80± 0.16 2.79 2.31 3.26 2.71± 0.21 2.71 2.03 3.38 2.49± 0.18 2.49 1.98 3.05 1.87± 0.18 1.88 1.34 2.43 NM-0.5 3.99± 0.16 4.00 3.48 4.40 4.62± 0.26 4.61 3.69 5.41 3.98± 0.17 3.98 3.48 4.40 3.67± 0.24 3.67 2.83 4.54 NM-0.7 4.66± 0.13 4.67 4.18 5.01 6.07± 0.21 6.07 5.23 6.68 4.66± 0.13 4.67 4.15 5.01 5.35± 0.24 5.35 4.57 6.16 NM-0.9 4.81± 0.11 4.82 4.41 5.08 6.56± 0.12 6.57 5.89 6.83 4.81± 0.11 4.82 4.41 5.08 6.72± 0.20 6.73 6.04 7.32 IC 4.82± 0.11 4.83 4.36 5.11 6.57± 0.12 6.58 6.11 6.84 4.82± 0.11 4.83 4.36 5.11 7.00± 0.16 7.01 6.32 7.44 URN-0.2 2.93± 0.59 3.01 0.61 4.35 4.48± 0.74 4.59 1.16 5.91 2.85± 0.60 2.93 0.61 4.28 4.06± 0.86 4.16 0.70 6.22 URN-0.5 1.96± 0.79 2.00 0.12 3.75 3.34± 1.07 3.49 0.21 5.48 1.80± 0.77 1.80 0.08 3.60 2.62± 1.07 2.61 0.04 5.58 SP/Walsh 2.46± 0.13 2.46 1.90 2.88 2.79± 0.21 2.78 2.10 3.57 2.27± 0.14 2.27 1.85 2.73 0.00± 0.00 0.00 0.00 0.00 SP/Conitzer 1.92± 0.17 1.93 1.42 2.44 1.86± 0.23 1.85 1.24 2.76 1.67± 0.18 1.67 1.10 2.15 0.00± 0.00 0.00 0.00 0.00 SC 2.76± 0.36 2.78 1.54 3.62 3.39± 0.35 3.41 2.24 4.34 2.48± 0.28 2.50 1.48 3.10 1.63± 0.40 1.64 0.30 2.76 1D EUC-cube 1.36± 0.43 1.38 0.27 2.67 1.69± 0.46 1.71 0.33 3.18 0.97± 0.30 0.98 0.05 1.79 0.00± 0.00 0.00 0.00 0.00 2D EUC-cube 2.88± 0.41 2.90 1.60 3.92 3.69± 0.55 3.73 1.69 5.05 2.59± 0.40 2.60 1.30 3.57 2.81± 0.62 2.85 0.81 4.09 3D EUC-cube 3.42± 0.37 3.45 2.05 4.43 4.42± 0.47 4.45 2.84 5.68 3.25± 0.37 3.26 1.99 4.36 3.57± 0.58 3.60 1.59 5.23 4D EUC-cube 3.70± 0.33 3.72 2.61 4.48 4.85± 0.43 4.87 3.47 5.95 3.60± 0.33 3.61 2.59 4.46 4.04± 0.58 4.05 2.20 5.62 5D EUC-cube 3.88± 0.32 3.90 2.62 4.74 5.09± 0.38 5.12 3.69 6.02 3.82± 0.33 3.83 2.62 4.73 4.29± 0.58 4.31 2.26 5.80 GS/cat 0.00± 0.00 0.00 0.00 0.00 6.48± 0.17 6.51 5.86 6.89 0.00± 0.00 0.00 0.00 0.00 6.01± 0.27 6.02 5.20 6.76 GS/bal 3.12± 0.13 3.14 2.61 3.39 0.00± 0.00 0.00 0.00 0.00 0.00± 0.00 0.00 0.00 0.00 3.13± 0.13 3.14 2.62 3.40 Real-life Elections: PrefLib We analyzed all elections with full strict ordering and at least 33 and at most 1515 candidates from PrefLib (Mattei and Walsh 2013). There are 3,6853,685 such elections. Out of these, we were able to compute distances for 3,1023,102 of them. The rest timed out within 11 hour per election time limit. Figure 13: The overall fraction of elections where GS/catGS/ , GS/balGS/ , GSGS, or Single-PeakedSingle- is the closest structured domain. Figure 14: An overview of closest domains per dataset and category. Figure 15: An overview of closest domains per the number of candidates within an election. We present our results using three figures. First, Figure 13 provides an overview of the entire dataset. Clearly, for roughly half of the elections satisfying the conditions above, the closest domain is Single-PeakedSingle- , and for roughly half of them, it is some variant of GSGS. Surprisingly, for 40.8%40.8\% of all the elections, the closest domain is GS/catGS/ ; however, it should be mentioned that this overview is highly affected by the dataset of Habermas, which on its own contains 2,7102,710 elections. Therefore, we also present an overview of the different datasets separately; see Figure 14. Moreover, we group different datasets based on their categories. Here, we can see that for datasets of sport events, GS/catGS/ , respectively GSGS domain is dominating. On the other hand, the elections based on charts are much more often close to the Single-PeakedSingle- domain. For experiment-based datasets, roughly half of the elections are Single-PeakedSingle- and the rest are GSGS, with a substantial portion of them being GS/catGS/ . Finally, we also explore how the distance to the closest domain changes with the increasing number of candidates. These results are depicted in Figure 15. The number of elections closest to the Single-PeakedSingle- domain does not have any intuitive explanation. However, there is a clear indication that, with the increasing number of candidates, the proportion of elections where some GSGS domain is the closest is increasing at the expense of the GS/catGS/ domain. E.3 Additional material for Section 5.3 Regarding the winner-retaining experiment, we also evaluate the Single Transferable Vote (STV) rule; see Figure 16. Because our experimental setup strictly considers single-winner elections, the STV mechanism effectively operates as a standard iterative elimination process. The threshold for victory is established by the Droop quota, q, which in a single-seat scenario simplifies to an absolute majority requirement q=⌊n2⌋+1q= n2 +1. If no candidate secures this quota, the candidate with the fewest first-preference votes is eliminated, and their ballots are transferred to the voters’ next available preferences. Although our experiment utilizes the Weighted Inclusive Gregory (WIG) method, surplus vote redistribution is not triggered, as the election concludes immediately once the quota is met. For scoring-based voting methods, we evaluate the impact of domain transformations on the original winners by analyzing their score differences. To ensure comparability, we first apply min-max normalization to the candidates’ scores in each election. Next, when comparing an original election to its closest transformed counterparts, we identify the smallest score difference experienced by any of the original winning candidates. This minimal score difference is then averaged across all the closest transformed elections associated with that single original election. Finally, we compute the grand mean of these values across all sampled elections, alongside the standard error of the mean; see . Figure 16: Probability of retaining original winners (success rate) under the STV voting rule for GS/catGS/ , GS/balGS/ , GSGS, and Single-PeakedSingle- projections. Appendix F ILP for Nearly GS-Caterpillar Election We fix an arbitrary ordering ⊳ on the candidate set C. This ordering is used only for indexing in constraints, and whenever we write a⊳ba b, we refer to it. For the relative order of two candidates in an input vote v and in its corresponding vote v′v in the closest GS/catGS/ election, we write ≻v _v and ≻v′ _v , respectively. Finally, for the mapping φ=(φ1,…,φm) =( _1,…, _m) of the candidates to leaves and a pair of candidates a,b∈Ca,b∈ C, we write a≻φba _ b to indicate that a precedes b in φ . We will use the following constants: 1. Input vote position constants. For every voter v∈Vv∈ V and pair of candidates a⊳ba b, the value of pabv∈0,1p^v_ab∈\0,1\ indicates their relative order in the input vote v. Here, pabv=1p^v_ab=1 if a≻vba _vb, and pabv=0p^v_ab=0 otherwise. We will use the following binary variables: 1. Mapping variables. For every pair of candidates a⊳ba b, the value of sab∈0,1s_ab∈\0,1\ indicates their relative order in the leaf mapping φ as sab=1s_ab=1 if a≻φba _ b and sab=0s_ab=0 otherwise. 2. Flip variables. For every voter v∈Vv∈ V and candidate a∈Ca∈ C, the value of fav∈0,1f^v_a∈\0,1\ indicates whether the voter decides to prepend the candidate a before the candidates that appear below in φ in the resulting vote v′v , in which case fav=0f^v_a=0, or append the candidate a to the rest of φ , in which case fav=1f^v_a=1. 3. Resulting votes position variables. For every voter v∈Vv∈ V and every pair of candidates a⊳ba b, the value of rabv∈0,1r^v_ab∈\0,1\ indicates the relative order of a and b in the resulting vote v′v . Here, rabv=1r^v_ab=1 if a≻v′ba _v b and rabv=0r^v_ab=0 otherwise. We will use two types of constraints: 1. Mapping validity constraints to ensure the leaf mapping variables encode a valid linear order. Antisymmetry is enforced by the variables encoding itself; hence we only need to ensure the transitivity by forbidding directed 3-cycles with the following two constraints: sab+sbc+(1−sac) s_ab+s_bc+(1-s_ac) ≤2∀a⊳b⊳c∈C ≤ 2 ∀ a b c∈ C (1−sab)+(1−sbc)+sac (1-s_ab)+(1-s_bc)+s_ac ≤2∀a⊳b⊳c∈C ≤ 2 ∀ a b c∈ C Note that it is enough to consider only these two constraints – restricting to triples with a⊳b⊳ca b c does not exclude any case. For example, the 3-cycle a⊲b⊳ca b c is the same 3-cycle as b⊳a⊳cb a c or b⊳c⊳ab c a (depending on whether a⊲ca c or c⊲ac a). 2. Group-separability constraints to ensure that the resulting votes belong to the caterpillar domain (Tcat,φ)D(T^cat, ). This is enforced by the following constraints for all v∈Vv∈ V and a⊳b∈C:a b∈ C: rabv r^v_ab =1−fva if a≻φb =1-f^v_a~~~~ if a _ b rabv r^v_ab =fvb if b≻φa =f^v_b~~~~~~~~~~~ if b _ a These constraints are linearized in a standard way as follows: rabv r^v_ab ≤(1−fav)+(1−sab)∀v∈V∀a⊳b∈C ≤(1-f^v_a)+(1-s_ab) ∀ v∈ V~~∀ a b∈ C rabv r^v_ab ≥(1−fav)−(1−sab)∀v∈V∀a⊳b∈C ≥(1-f^v_a)-(1-s_ab) ∀ v∈ V~~∀ a b∈ C rabv r^v_ab ≤fbv+sab∀v∈V∀a⊳b∈C ≤ f^v_b+s_ab ~~~~~~~~~~~~~~~~~~~~∀ v∈ V~~∀ a b∈ C rabv r^v_ab ≥fbv−sab∀v∈V∀a⊳b∈C ≥ f^v_b-s_ab ~~~~~~~~~~~~~~~~~~~~∀ v∈ V~~∀ a b∈ C Observe that when sab=1s_ab=1 for a⊳ba b, the first two constraints yield rabv≤(1−fav)r^v_ab≤(1-f^v_a) and rabv≥(1−fav)r^v_ab≥(1-f^v_a), forcing rabv=1−favr^v_ab=1-f^v_a, while the third and fourth inequalities hold regardless of the value of fbvf^v_b; the reverse holds for sab=0s_ab=0. Therefore, in the rest of the proof, we work directly with the compact formulation instead of the linearized inequalities. To compute the minimum swap distance between the input vote v and the resulting vote v′v , we minimize the number of inversions between them. Hence, as the objective function we set min∑v∈V∑a⊳b∈C|pvab−rvab|. _v∈ V _a b∈ C|p^v_ab-r^v_ab|. This can be linearized as min∑v∈V∑a⊳b∈Cpabv(1−rabv)+(1−pabv)rabv _v∈ V _a b∈ Cp^v_ab(1-r^v_ab)+(1-p^v_ab)r^v_ab In total, the ILP formulation uses (nm2)O(nm^2) variables and ((m+n)m2)O((m+n)m^2) constraints. We now prove the correctness of the construction. Forward implication. Assume that φ=(φ1,…,φm) =( _1,…, _m) is a mapping to the leaves of the caterpillar tree TcatT^cat and that V′=(v1′,…,vn′)V =(v _1,…,v _n) is a list of votes from the (Tcat,φ)D(T^cat, ) domain. We show that then there exists an assignment to the ILP variables satisfying the constraints. We define the assignment as follows: for every pair of candidates a⊳ba b, we set sab=1s_ab=1 if and only if a≻φba _ b, and for every v∈Vv∈ V and a⊳ba b, set rabv=1r^v_ab=1 if and only if a≻v′ba _v b. Finally, based on the resulting vote v′v , we set the flip variables as follows. For a vote v∈Vv∈ V and every candidate a≠φma≠ _m, i.e. every candidate that is not the last in the mapping φ , we set fav=0f^v_a=0 if and only if a≻v′ba _v b for every b with a≻φba _ b, i.e. for every candidate that follows a in the leaf mapping φ . The value of the flip variable fφmvf^v_ _m for the last candidate φm _m in φ may be set arbitrarily. We argue that this assignment of variables satisfies the ILP constraints. First, assume for contradiction that the mapping validity constraints are not satisfied. That is, there exists a triple of candidates a⊳b⊳ca b c such that sab+sbc+(1−sac)=3s_ab+s_bc+(1-s_ac)=3 or (1−sab)+(1−sbc)+sac=3(1-s_ab)+(1-s_bc)+s_ac=3. In the first case, this implies that sab=sbc=1s_ab=s_bc=1 and sac=0s_ac=0. However, this would yield a≻φba _ b, b≻φcb _ c and c≻φac _ a. i.e., a directed 3-cycle in the relation induced by the s variables. But, since sab=1s_ab=1 if and only if a≻φba _ b, this would imply that ≻φ _ is not transitive, contradicting the fact that φ is a valid linear order. The second case would then imply sab=sbc=0s_ab=s_bc=0 and sac=1s_ac=1 and the existence of a reversed directed 3-cycle; again, a contradiction. Next, we show that the assignment satisfies the group-separability constraints. Let a and b be a pair of candidates such that a⊳ba b. Based on their relative position in φ , we distinguish two cases. Case A: a≻φba _ b. In this case, the first constraint rabv=1−favr^v_ab=1-f^v_a applies. Based on the relative order of a and b in the resulting vote v′v , we distinguish two subcases. If a≻v′ba _v b, then the resulting vote variable was set to rabv=1r^v_ab=1, and the flip variable was set to fav=0f^v_a=0 (as b is after a in φ and appears below a in the resulting vote v′v ). If b≻v′ab _v a, then the variables were set to rabv=0r^v_ab=0 and fav=1f^v_a=1. In both cases, the equality is satisfied. Case B: b≻φab _ a. In this case, the second constraint rabv=fbvr^v_ab=f^v_b applies. Again, based on the relative order of a and b in ≻v′ _v , there are two possibilities: If a≻v′ba _v b, then the variables were set to rabv=1r^v_ab=1 and fbv=1f^v_b=1. If b≻v′ab _v a, then the variables were set to rabv=0r^v_ab=0 and fbv=0f^v_b=0. Again, in both cases, the equality holds. Backward implication. Assume now that we have a valid assignment to the variables that satisfies the constraints of our ILP. We show that the assignment corresponds to a mapping φ and a list of votes V′=(v1′,…,vn′)V =(v _1,…,v _n) from the caterpillar domain. For convenience, we extend the resulting vote variables antisymmetrically to all ordered pairs by setting rbav:=1−rabvr^v_ba:=1-r^v_ab for every a⊳ba b. First, observe that by the definition of the mapping variables s, the induced relation φ is irreflexive and antisymmetric (as we have exactly one variable defined per each unordered pair a,b∈Ca,b∈ C, indicating their relative order). The constraints forbidding directed 3-cycles then enforce transitivity, so φ is a strict linear order on C. Next, we argue that the resulting vote variables r induce a strict linear order as well. Irreflexivity and antisymmetry follow by definition, by the same argument as for mapping variables. Transitivity is enforced by the transitivity of the s variables together with the flip variables f and vote group-separability constraints, as we now argue. Assume that the relation induced by r is not transitive. Therefore, there exists a directed 3-cycle on some triple of candidates a⊳b⊳ca b c. Similarly as in the description of the mapping validity constraints, this implies that either rabv+rbcv+(1−racv)=3r^v_ab+r^v_bc+(1-r^v_ac)=3 or (1−rabv)+(1−rbcv)+racv=3(1-r^v_ab)+(1-r^v_bc)+r^v_ac=3. We now argue that this leads to a contradiction. First assume that rabv+rbcv+(1−racv)=3r^v_ab+r^v_bc+(1-r^v_ac)=3. This would mean that rabv=rbcv=1r^v_ab=r^v_bc=1 and racv=0r^v_ac=0. We proceed by case analysis based on how a,b,ca,b,c are ordered by ≻φ _ . If a≻φb≻φca _ b _ c, then from the first group-separability constraint and rabv=rbcv=1r^v_ab=r^v_bc=1 we know that fav=fbv=0f^v_a=f^v_b=0. But racv=0r^v_ac=0 and the first group-separability constraint imply that fav=1f^v_a=1, a contradiction. Next, consider the case when b≻φa≻φcb _ a _ c, then rabv=1r^v_ab=1 together with the second group-separability constraint yield that fbv=1f^v_b=1, and rbcv=1r^v_bc=1 together with the first group-separability constraint imply fbv=0f^v_b=0; a contradiction. For other possible orderings of a,b,ca,b,c by ≻φ _ one can argue analogously. Dual arguments then hold for the case when (1−rabv)+(1−rbcv)+racv=3(1-r^v_ab)+(1-r^v_bc)+r^v_ac=3, with the values of fvf^v flipped from 00 to 11 and vice-versa. Finally, we show that the votes induced by the r variables belong to the caterpillar domain (Tcat,φ)D(T^cat, ). Let a be an arbitrary candidate. We show that in every vote v′v , a must be ranked either above all b such that a≻φba _ b, or below. We proceed by case analysis on the ⊳ -order of a and b. First, in case a⊳ba b, the relative order of the candidates is determined by the constraint rabv=1−favr^v_ab=1-f^v_a. We distinguish two subcases. If fav=0f^v_a=0, then rabv=1r^v_ab=1, yielding that a is ranked above all b such that a≻φba _ b. If fav=1f^v_a=1, then rabv=0r^v_ab=0 , yielding that a is ranked below all b such that a≻φba _ b. Second, in case b⊳ab a, the relative order of a and b is determined by the second constraint rbav=favr^v_ba=f^v_a. Again, we have two possibilities. If fav=0f^v_a=0, then rbav=0r^v_ba=0, yielding that a is ranked above b. If fav=1f^v_a=1, then rbav=1r^v_ba=1, yielding that a is ranked below b. Since b was an arbitrary candidate such that a≻φba _ b, it follows that a is ranked either above or below all candidates following in φ , and hence the votes V′=(v1′,…,vn′)V =(v _1,…,v _n) belong to (Tcat,φ)D(T^cat, ). Since in both directions the objective is equal to the total swap distance between the corresponding votes, the optimal ILP solutions correspond to the closest GS/catGS/ elections. Appendix G ILP for Nearly GS-Balanced Election Given an integer k, we write [k]0[k]_0 to denote [k]∪0[k]∪\0\. We assume that the number of candidates m is a power of two. Throughout this section, we denote by TbalT^bal a perfect binary QQ-tree with m leaves. To simplify the notation, we identify each candidate a∈Ca∈ C with the leaf φ(a) (a) it is mapped to. In particular, we speak of candidates lying in the subtrees of TbalT^bal and write lca(a,b)lca(a,b) for the lowest common ancestor of a and b. We use the following constants: 1. Input vote position constants. For every voter v∈Vv∈ V and every ordered pair of candidates a≠b∈Ca≠ b∈ C, the value of pabv∈0,1p^v_ab∈\0,1\ encodes the position of a and b in the input vote. The value is 11 if a≻vba _vb and 00 otherwise. 2. L=log2m∈ℕL= _2m to denote the depth of the tree TbalT^bal. Levels are indexed by ℓ∈[L−1]0 ∈[L-1]_0, i.e. the root vertex is on level ℓ=0 =0. We introduce the following variables: 1. The tree variables Taℓ∈0,1T_a ∈\0,1\ to encode the positions of candidates in the leaf mapping φ as a binary string. Equal to 00 if the candidate a is in the left subtree of its ancestor node at level ℓ , and 11 otherwise. 2. The flip variables Fvaℓ∈0,1F_va ∈\0,1\. Intuitively, at each inner node u of TbalT^bal, the voter v decides whether the candidates in the left subtree of u should be ranked above the candidates in the right subtree of u, following the order of the mapping φ , or below them (in which case a flip occurs). The variable is equal to 11 if voter v flips the order at candidate a’s unique ancestor on level ℓ , and 00 otherwise. 3. The resulting vote variables. For every voter v∈Vv∈ V and every ordered pair of candidates a≠b∈Ca≠ b∈ C, the value of rabv∈0,1r^v_ab∈\0,1\ indicates the relative order of a and b in the resulting vote v′v . Equals to 11 if a≻v′ba _v b in the resulting vote v′v , and 00 otherwise. 4. Auxiliary variables. In the construction, we further use binary variables tabℓ,Sab<ℓ,Aabℓ,αvaℓt _ab,S^< _ab,A _ab,α _va and βvabℓ∈0,1β _vab∈\0,1\, whose meaning we specify with the constraints that use them. We introduce the following constraints: 1. The tree constraints. In order to have a valid mapping φ of the candidates to the leaves of TbalT^bal, there need to exist m unique binary encodings via the tree variables. This means that, for every pair of candidates a≠b∈Ca≠ b∈ C, there must exist at least one level ℓ∈[L−1]0 ∈[L-1]_0 such that Taℓ≠TbℓT _a≠ T _b. Let tabℓ:=|Taℓ−Tbℓ|t_ab :=|T _a-T _b| denote the difference of the variables on level ℓ . Then we can express this requirement through the constraints as follows: tabℓ t _ab =|Taℓ−Tbℓ| =|T _a-T _b| ∀a≠b∈C ∀ a≠ b∈ C ∀ℓ∈[L−1]0 ∀ ∈[L-1]_0 ∑ℓ=0L−1 _ =0^L-1 tabℓ≥1 t _ab≥ 1 ∀a≠b∈C ∀ a≠ b∈ C The first constraint can be linearized as: tabℓ t _ab ≥Taℓ−Tbℓ ≥ T _a-T _b tabℓ t _ab ≥Tbℓ−Taℓ ≥ T _b-T _a tabℓ t _ab ≤Taℓ+Tbℓ ≤ T _a+T _b tabℓ t _ab ≤2−(Taℓ+Tbℓ) ≤ 2-(T _a+T _b) 2. The flip constraints. Let a≠b∈Ca≠ b∈ C be a pair of candidates. Observe that the relative position of a and b in the resulting vote v′v is decided at the flip decision at their lowest common ancestor lca(a,b)lca(a,b) node in TbalT^bal; in all levels strictly above, the candidates belong to the same subtrees. Therefore, we need to enforce that in all inner nodes on the path from the root to lca(a,b)lca(a,b) (including), the flip variables for a and b must have the same values. To do so, we use auxiliary variable Sab<ℓ∈0,1S^< _ab∈\0,1\ that is equal to 11 if a and b have the same ancestor in all levels ℓ′<ℓ < , and 00 otherwise. Trivially, strictly before the root level ℓ=0 =0, all candidates have the same ancestor and therefore we set Sab<0=1S^<0_ab=1 for all a≠b∈Ca≠ b∈ C. For every other level ℓ≥1 ≥ 1, we require that Sab<ℓ=1S^< _ab=1 if and only if the binary addresses of a and b (encoded via the tree variables) agree on all levels strictly below ℓ . That is, using the auxiliary variable tabℓ′:=|Taℓ′−Tbℓ′|t _ab:=|T _a-T _b| from the tree constraints, we require that Sab<ℓ=1⇔tabℓ′=0S^< _ab=1 t _ab=0 for all ℓ′<ℓ ~<~ , linearized as: Sab<ℓ S^< _ab ≤1−tabℓ′∀ℓ′<ℓ ≤ 1-t _ab~~~∀ < Sab<ℓ S^< _ab ≥1−∑ℓ′=0ℓ−1tabℓ′ ≥ 1- _ =0 -1t _ab Finally, for any level ℓ∈[L−1]0 ∈[L-1]_0 where a and b have the same ancestor, we require that the flip variables for a and b must be equal. Formally, for every pair a≠b∈Ca≠ b∈ C, every voter v∈Vv∈ V and every level ℓ∈[L−1]0 ∈[L-1]_0 we require that: Sab<ℓ=1⇒Fvaℓ=Fvbℓ S^< _ab=1 F _va=F _vb Linearized as: 1−Sab<ℓ≥Fvaℓ−Fvbℓ 1-S^< _ab≥ F _va-F _vb 1−Sab<ℓ≥Fvbℓ−Fvaℓ 1-S^< _ab≥ F _vb-F _va 3. The group-separability constraints. Finally, we tie the leaf mapping φ and the flip variables and enforce that the resulting votes belong to (Tbal,φ)D(T^bal, ). Recall that the relative position of two candidates a and b is determined by the decision (flip) at lca(a,b)lca(a,b). To encode the lowest common ancestor level, we use an auxiliary variable AabℓA _ab, which we require to equal 11 if a and b agree in all levels strictly below ℓ and disagree in their binary addresses at ℓ . Formally, we enforce that Aabℓ=1A _ab=1 if and only if Sab<ℓ=1S^< _ab=1 and tabℓ=|Taℓ−Tbℓ|=1t _ab=|T _a-T _b|=1. Additionally, we require that exactly one ℓ∈[L−1]0 ∈[L-1]_0 satisfies Aabℓ=1A _ab=1. We express these two requirements with the following four constraints: Aabℓ A _ab ≤Sab<ℓ ≤ S^< _ab ∀a≠b∈C ∀ a≠ b∈ C ∀ℓ∈[L−1]0 ∀ ∈[L-1]_0 Aabℓ A _ab ≤tabℓ ≤ t _ab ∀a≠b∈C ∀ a≠ b∈ C ∀ℓ∈[L−1]0 ∀ ∈[L-1]_0 Aabℓ A _ab ≥Sab<ℓ+tabℓ−1 ≥ S^< _ab+t _ab-1 ∀a≠b∈C ∀ a≠ b∈ C ∀ℓ∈[L−1]0 ∀ ∈[L-1]_0 ∑ℓ=0L−1 _ =0^L-1 Aabℓ=1 A _ab=1 ∀a≠b∈C ∀ a≠ b∈ C To encode the relative position of a and b in the resulting vote v′v , we further use an auxiliary variable αvaℓ∈0,1α _va∈\0,1\. Let u be the ancestor of a on level ℓ . The α variable expresses whether on level ℓ , the candidate a should be ranked above the candidates in the subtree of u not containing a, or below. In particular, if Taℓ=0T _a=0 and Fvaℓ=0F _va=0 (or Taℓ=1T _a=1 and Fvaℓ=1F _va=1), voter v ranks a above the other subtree, in which case we require αvaℓ=0α _va=0. Symmetrically, if Taℓ=0T _a=0 and Fvaℓ=1F _va=1 (or Taℓ=1T _a=1 and Fvaℓ=0F _va=0), a should be ranked below all candidates in the other subtree, in which case we require αvaℓ=1α _va=1. Formally, we require that αvaℓ=|Taℓ−Fvaℓ|∀v∈V∀a∈C∀ℓ∈[L−1]0. α _va=|T _a-F _va|~~~∀ v∈ V~~∀ a∈ C~~∀ ∈[L-1]_0. This constraint can be linearized analogously to the tree constraint tabℓ=|Taℓ−Tbℓ|t _ab=|T _a-T _b|. To connect the resulting vote variables, we additionally introduce auxiliary variable βvabℓ∈0,1β _vab∈\0,1\. For a pair of candidates a and b and level ℓ∈[L−1]0 ∈[L-1]_0, we want βvabℓ=1β _vab=1 if and only if ℓ is the level containing lca(a,b)lca(a,b) and a is supposed to be ranked above b, i.e., Aabℓ=1A _ab=1 and αvaℓ=0α _va=0. Formally, for all v∈Vv∈ V, a≠b∈Ca≠ b∈ C and ℓ∈[L−1]0 ∈[L-1]_0 we enforce that βvabℓ=Aabℓ(1−αvaℓ). β _vab=A _ab(1-α _va). This can be linearized for every v∈Vv∈ V, every a≠b∈Ca≠ b∈ C, and every ℓ∈[L−1]0 ∈[L-1]_0 as βvabℓ β _vab ≤Aabℓ ≤ A _ab βvabℓ β _vab ≤1−αvaℓ ≤ 1-α _va βvabℓ β _vab ≥Aabℓ−αvaℓ ≥ A _ab-α _va βvabℓ β _vab ≥0 ≥ 0 Summing across all levels ℓ∈[L−1]0 ∈[L-1]_0, we then determine the final order of a and b as follows: rabv=∑ℓ=0L−1βvabℓ∀v∈V∀a≠b∈C r^v_ab= _ =0^L-1β _vab~~~∀ v∈ V~~~∀ a≠ b∈ C Objective Function. To compute the minimal swap distance between the input and resulting votes, we minimize the number of inversions between the original vote variables and resulting vote variables: min∑v∈V∑a⊳b∈C|pvab−rvab| _v∈ V _a b∈ C|p^v_ab-r^v_ab| Here, ⊳ is an arbitrary fixed ordering on the candidate set C, used so each pair of candidates is counted exactly once. The objective function can be linearized as: min∑v∈V∑a⊳b∈Cpabv(1−rabv)+(1−pabv)rabv. _v∈ V _a b∈ Cp^v_ab(1-r^v_ab)+(1-p^v_ab)r^v_ab. In total, the ILP formulation uses (nm2logm)O(nm^2 m) variables and ((n+logm)m2logm)O((n+ m)m^2 m) constraints. We now prove the correctness. Forward implication. Let φ=(φ1,…,φm) =( _1,…, _m) be a mapping of the candidates to the leaves of TbalT^bal, ordered from the left-most leaf to the right-most, and let V′=(v1′,…,vn′)V =(v _1,…,v _n) be a list of votes from (Tbal,φ)D(T^bal, ). We show that there exists an assignment of the variables that satisfies the ILP constraints. First, we assign the values to the tree variables T according to φ . For the i-th candidate φi _i, we express its position i in binary, with the position of the first candidate φ1 _1 being encoded as all zeros. Then, we set TφiℓT _ _i to be the value of the ℓ -th position of the binary string encoding φi _i’s position. Next, given a vote v′v , we assign the values of the flip variables F as follows. Since v′∈(Tbal,φ)v (T^bal, ), the candidates mapped by φ to the leaves of every subtree form a contiguous block in v′v . For each level ℓ∈[L−1]0 ∈[L-1]_0 and each inner node u at level ℓ , we set Fvaℓ:=0F _va:=0 for every candidate a in the subtree of u if the candidates in the left subtree of u lie in the first half of u’s block in vote v′v , and Fvaℓ:=1F _va:=1 otherwise. Further, given a vote v′v and pair of candidates a≠b∈Ca≠ b∈ C, we set rabv=1r^v_ab=1 if and only if a≻v′ba _v b. Finally, we set the values of the auxiliary variables t,S,A,αt,S,A,α and β according to their defining equations. We now argue that this assignment of variables satisfies the constraints of our ILP. The tree constraints are clearly satisfied, as the values of the T variables correspond to the binary encoding of a position of a candidate a in the leaf ordering φ , and the encodings are unique. Next, we verify the flip constraints. Let v∈Vv∈ V be any voter, a≠b∈Ca≠ b∈ C an arbitrary pair of candidates and ℓ the level containing their lowest common ancestor node. We argue that Fvaℓ′=Fvbℓ′F _va=F _vb for every ℓ′≤ℓ ≤ . By the definition of the lowest common ancestor, a and b share the path from ℓ up to the root. That is, for every ℓ′≤ℓ ≤ , they lie in a subtree of the same inner node u at level ℓ′ . As our assignment gives the same value to all candidates that lie in the subtree of u, we get that Fvaℓ′=Fvbℓ′F _va=F _vb. Next, observe that there is indeed exactly one ℓ∈[L−1]0 ∈[L-1]_0 such that Aabℓ=1A _ab=1: for any pair of candidates a≠b∈Ca≠ b∈ C, it is the smallest ℓ such that Taℓ≠TbℓT _a≠ T _b, i.e. the first bit, where their binary addresses differ. For every pair, this ℓ is unique. Finally, we verify the group-separability constraints. Let a≠b∈Ca≠ b∈ C be a pair of candidates, u their lowest common ancestor, and ℓ the level containing u. First, observe that a and b lie in different subtrees of u. Second, since v′v is in the domain (Tbal,φ)D(T^bal, ), the left and right subtrees of u form two contiguous blocks. In other words, the relative position of a and b is determined precisely at u and the level ℓ . To show the correctness, we need to show that the constraint rabv=∑ℓ=0L−1βvabℓr^v_ab= _ =0^L-1β _vab holds, where βvabℓ=Aabℓ(1−αvaℓ)β _vab=A _ab(1-α _va). Observe that by our construction, Aabℓ′=1A _ab=1 precisely (and only) at ℓ′=ℓ = , and hence the constraint collapses to rabv=1−αvaℓr^v_ab=1-α _va. We proceed by case analysis based on the relative order of a and b in v′v . First, assume that a≻v′ba _v b; then rabv=1r^v_ab=1 by our construction. Based on the relative order of a and b in ≻φ _ , we have two subcases. If a≻φba _ b, then a lies in the left subtree and b lies in the right subtree of u, i.e. Taℓ=0T _a=0 and Tbℓ=1T _b=1. Since a≻v′ba _v b, in the vote v′v , the block of candidates of the left subtree lies in the first half of u’s block, and our construction sets Fvaℓ=Fvbℓ=0F _va=F _vb=0, informally meaning the voter did not decide to flip the order at node u. It follows that αvaℓ=|Taℓ−Fvaℓ|=0=1−rabvα _va=|T _a-F _va|=0=1-r^v_ab as desired. Symmetrically, if b≻φab _ a, then a lies in the right subtree and b lies in the left subtree of u, i.e. Taℓ=1T _a=1 and Tbℓ=0T _b=0. Then the block of candidates of the left subtree lies behind the block of the candidates of the right subtree of u, and our construction sets Fvaℓ=1F _va=1. In this case, we again obtain that αvaℓ=|Taℓ−Fvaℓ|=0=1−rabvα _va=|T _a-F _va|=0=1-r^v_ab. The case when b≻v′ab _v a is symmetric, giving αvaℓ=1α _va=1 and rabv=0r^v_ab=0 instead. Backward implication. Assume we have an assignment to the variables that satisfies the ILP constraints. We show that this assignment corresponds to a valid mapping φ of candidates to the leaves of TbalT^bal and to a list of votes V′=(v1′,…,vn′)V ~=~(v _1,…,v _n) in (Tbal,φ)D(T^bal, ). For a candidate a∈Ca∈ C, consider the values of TaℓT _a for each ℓ∈[L−1]0 ∈[L-1]_0, ordered from 00 to L−1L-1, and concatenate them into a binary string. This gives us a binary encoded position for every candidate. Since we have L=log2mL= _2m levels, there are 2L=m2^L=m such strings. Moreover, these strings are guaranteed to be unique: our constraints ensure that for every pair of distinct candidates a≠b∈Ca≠ b∈ C, there exists at least one ℓ for which Taℓ≠TbℓT _a≠ T _b. Consequently, the values of T define a valid mapping φ of the candidates to the leaves of the tree. First, we argue that the relation induced by the resulting vote variables r is antisymmetric. Fix a pair of candidates a≠b∈Ca≠ b∈ C. By our constraints, there exists precisely one ℓ∈[L−1]0 ∈[L-1]_0 such that Aabℓ=1A _ab=1. Observe that then the constraint rabv=∑ℓ=0L−1Aabℓ(1−αvaℓ)r^v_ab= _ =0^L-1A _ab(1-α _va) collapses to rabv=Aabℓ(1−αvaℓ)=1−αvaℓr^v_ab=A _ab(1-α _va)=1-α _va, as for every other ℓ′≠ℓ ≠ the value of Aabℓ′=0A _ab=0. Without loss of generality, assume that Taℓ=0T _a=0 and Tbℓ=1T _b=1. By the flip constraints, we have Fvaℓ=FvbℓF _va=F _vb. Since αvcℓ=0⇔Tcℓ=Fvcℓα _vc=0 T _c=F _vc for any candidate c, it follows that exactly one c∈a,bc∈\a,b\ has αvcℓ=0α _vc=0, while the other has αvcℓ=1α _vc=1. Consequently, exactly one of rabvr^v_ab and rbavr^v_ba equals to 11, while the other equals to 00, and hence the relation is antisymmetric. Next, we argue that the values of rabvr^v_ab induce a transitive relation. Let a,b,c∈Ca,b,c∈ C be any triple of candidates and v∈Vv∈ V an arbitrary voter. We show that if rabv=1r^v_ab=1 and rbcv=1r^v_bc=1, then also racv=1r^v_ac=1. Let ℓab,ℓac _ab, _ac and ℓbc _bc denote the levels of the lowest common ancestors of the corresponding pairs of candidates. Let ℓ=minℓab,ℓac,ℓbc = \ _ab, _ac, _bc\. Note that two of these three values are equal. Let u be the lowest common ancestor of all three candidates a,b,ca,b,c. Since the tree is binary, one subtree of u needs to contain exactly one of the three candidates, while the other needs to contain the remaining two. The two pairs involving the separated candidate then need to have u as their lowest common ancestor, while the lowest common ancestor of the remaining pair lies in a level strictly below u. Based on which two levels among ℓab,ℓac _ab, _ac and ℓbc _bc are equal, we therefore distinguish three cases. First, if ℓab=ℓac=ℓ _ab= _ac= , the candidate a is separated at level ℓ and Taℓ≠Tcℓ=TbℓT _a≠ T _c=T _b. Since rabv=1r^v_ab=1 by our assumption, it follows from the constraint rabv=Aabℓ(1−αvaℓ)r^v_ab=A _ab(1-α _va) that αvaℓ=0α _va=0. As ℓ is the level containing lca(a,c)lca(a,c), it follows that racv=Aacℓ(1−αvaℓ)=1r^v_ac=A _ac(1-α _va)=1 as desired. For the second case, assume ℓ=ℓab=ℓbc = _ab= _bc, i.e, the candidate b is separated at level ℓ and Tbℓ≠Taℓ=TcℓT _b≠ T _a=T _c. Then, analogously to the previous case, rabv=1r^v_ab=1 yields αvaℓ=0α _va=0, and hence by the definition of αvaℓα _va, we get that Taℓ=FvaℓT _a=F _va. By the same argument, rbcv=1r^v_bc=1 implies αvbℓ=0α _vb=0 and Tbℓ=FvbℓT _b=F _vb. We know that up to the level containing the lowest common ancestor (including), the flip variables need to be equal, and in particular it must hold that Fvaℓ=Fvbℓ=FvcℓF _va=F _vb=F _vc. But then, by combining the facts that Taℓ=FvaℓT _a=F _va and Tbℓ=FvbℓT _b=F _vb, we obtain Taℓ=Fvaℓ=Fvbℓ=TbℓT _a=F _va=F _vb=T _b, a contradiction with our assumption that Taℓ≠TbℓT _a≠ T _b. The second case is, therefore, not possible. The third case is then analogous to the first. Here, assume that ℓ=ℓac=ℓbc = _ac= _bc, i.e., c is the separated candidate and Tcℓ≠Taℓ=TbℓT _c≠ T _a=T _b. Again, from rbcv=1r^v_bc=1 we obtain that αvbℓ=0α _vb=0 and hence Tbℓ=FvbℓT _b=F _vb. From our assumption that Taℓ=TbℓT _a=T _b we then get that Fvaℓ=FvbℓF _va=F _vb, and therefore αvaℓ=0α _va=0. Finally, since Aacℓ=1A _ac=1, we obtain that racv=1−αvaℓ=1r^v_ac=1-α _va=1, as desired. Finally, we argue that the constructed votes belong to (Tbal,φ)D(T^bal, ). Let v∈Vv∈ V be an arbitrary voter and v′v the vote induced by the r variables. We show that for every inner node u in the tree TbalT^bal, all candidates in the left subtree of u are either ranked above all candidates in the right subtree of u, or below. Let ℓ be the level containing u. By our constraints, any pair of candidates a,ba,b in the subtree of u shares the same value of the flip variable at ℓ : a and b agree on all levels ℓ′<ℓ < , so Sab<ℓ=1S^< _ab=1 and the constraint Sab<ℓ=1⟹Fvaℓ=FvbℓS^< _ab=1 F _va=F _vb forces the flip variables to be equal. Assume now that a is a candidate in the left subtree of u, and b is a candidate in the right subtree of u, and that lca(a,b)=ulca(a,b)=u. In this case, Taℓ=0T _a=0, Tbℓ=1T _b=1 and Aabℓ=1A _ab=1. The constraints then yield rabv=1−αvaℓ=1−|Taℓ−Fvaℓ|r^v_ab=1-α _va=1-|T _a-F _va|. Hence, if Fvaℓ=0F _va=0, i.e., the voter does not flip the order at u, rabv=1r^v_ab=1 and a is ranked above b; if Fvaℓ=1F _va=1, we get that rabv=0r^v_ab=0 and a is ranked below b in the vote v′v . Since all candidates contained in the subtree rooted at u share the same flip value at u, say f, it follows that every candidate of the left subtree is ranked above every candidate in the right subtree (in case f=0f=0), or below every candidate in the right subtree (in case f=1f=1). As this holds at every inner node of TbalT^bal, it follows that the votes obtained from the r variables belong to (Tbal,φ)D(T^bal, ). Since in both directions the objective equals the total swap distance between the input and resulting votes, the optimal ILP solutions correspond to the closest GS/balGS/ elections.