# Toward Completing the Picture of Control in Schulze and Ranked Pairs
Elections: Supplementary Material

Cynthia Maushagen  David Niclaus  Paul Nüsken  Jörg Rothe &Tessa Seeger
Heinrich-Heine-Universität Düsseldorf, MNF, Institut für Informatik,
Düsseldorf, Germany
{cynthia.maushagen, david.niclaus, paul.nuesken, rothe<EMAIL_ADDRESS>
###### Abstract

Both Schulze and ranked pairs are voting rules that satisfy many natural,
desirable axioms. Many standard types of electoral control (with a chair
seeking to change the outcome of an election by interfering with the election
structure) have already been studied. However, for control by replacing
candidates or voters and for (exact) multimode control that combines multiple
standard attacks, many questions remain open. We solve a number of these open
cases for Schulze and ranked pairs. In addition, we fix a flaw in the
reduction of Menton and Singh [IJCAI 2013] showing that Schulze is resistant
to constructive control by deleting candidates and re-establish a
vulnerability result for destructive control by deleting candidates. In some
of our proofs, we study variants of $s$-$t$ vertex cuts in graphs that are
related to our control problems.

##  1 Introduction

†† This paper is to appear in the proceedings of IJCAI 2024 and in addition
contains the supplementary material.

Elections play a fundamental role in decision-making processes of societies.
Both the Schulze method Schulze (2011, 2023) and the ranked pairs method
Tideman (1987) satisfy many natural, desirable axioms.

The Schulze method is a relatively new voting rule and has gained unusual
popularity over the past decade due to its outstanding axiomatic properties.
In the real world, organizations like the Wikimedia Foundation, Kubernetes, or
the Debian Vote Engine Schulze (2023) have used it in their decision-making
processes. Although winner determination with the Schulze method is fairly
complicated compared to most other voting rules, it can still be done in
polynomial time Schulze (2011); Sornat et al. (2021). The ranked pairs method
was specifically designed to satisfy the independence of clones criterion
Tideman (1987). In general, its axiomatic properties are as outstanding as
Schulze’s. That ranked pairs is barely widespread might be due to the fact
that winner determination strongly depends on the handling of ties: When using
“parallel universe tie-breaking” Conitzer et al. (2009), the winner
determination problem is $\mathrm{NP}$-complete. However, it becomes tractable
when defining ranked pairs as a resolute rule by using a fixed tie-breaking
method Brill and Fischer (2012).

We study _electoral control_ where a so-called _election chair_ (or, simply
_chair_) attempts to change the outcome of an election by changing its
structure. Common examples are adding, deleting, partitioning Bartholdi III et
al. (1992); Hemaspaandra et al. (2007), or replacing Loreggia et al. (2015)
candidates or voters. In addition to these control types, we also study
multimode control Faliszewski et al. (2011) where the chair can combine
several attacks into one. For each corresponding electoral control problem,
there is a constructive case Bartholdi III et al. (1992) where the goal is to
make a favored candidate win the election, and a destructive case Hemaspaandra
et al. (2007) where the chair’s aim is to prevent a despised candidate from
winning. It is natural to assume that it is beneficial for a voting rule to be
immune to control, i.e., it is impossible to change the outcome of an election
by that control type. However, immunity to control types does not occur
often.111Immunity to control corresponds to strategyproofness against
manipulation (a.k.a. strategic voting), since both notions formalize the
impossibility to reward strategic behaviour with success.  In fact, most
voting rule are susceptible to control Faliszewski and Rothe (2016), i.e.,
control is possible in a least some instances. Computational intractability
can then be seen as a form of resistance to control: If it is computationally
hard for an agent to decide if the goal of the attack can be achieved, it may
deter the attacker from spending resources on this task. On the other hand,
not all forms of control are malicious. In many cases, deciding if a control
action can be achieved in polynomial time is beneficial for deciding whether
to allocate resources to, e.g., a voter drive or spawning new nodes in the
context of large clusters. We call a voting rule vulnerable to a control type
if the corresponding decision problem can be decided in polynomial time.

While many standard control types have already been studied for Schulze and
ranked pairs (Table 1), control by replacing candidates or voters and exact
multimode control remained open. There are many real world situations where a
chair must adhere to a specific number of candidates, e.g., if the election’s
size is predetermined and a fixed number of candidates are already nominated,
forcing the chair to nominate exactly the missing number of candidates. The
restriction makes control impossible in some situations, where control by
adding fewer candidates would be successful. Other (practical) settings
include autonomous agents where, e.g., the size of the cluster is
predetermined. A chair may be able to influence some part of the cluster, but
is forced to adhere to the overall determined size (examples can be found in
the supplementary material).

### Related Work:

Bartholdi et al. Bartholdi III et al. (1992) introduced constructive control
types and Hemaspaandra et al. Hemaspaandra et al. (2007) the corresponding
destructive cases. Control by replacing candidates or voters was introduced by
Loreggia et al. Loreggia et al. (2015), while Faliszewski et al. Faliszewski
et al. (2011) introduced and studied multimode control. Erdélyi et al. Erdélyi
et al. (2021) provide an extensive study and overview of various control
problems, including replacing candidates or voters and also multimode
control.222Besides for voting, control has also been studied in, e.g.,
judgment aggregation Baumeister et al. (2020) and for weighted voting games
Rey and Rothe (2018); Kaczmarek and Rothe (2024) and graph-restricted weighted
voting games Kaczmarek et al. (2023).

Other types of strategic influence on elections are _manipulation_ , where a
voter or a group of voters state their preferences strategically (i.e.,
untruthfully), and _bribery_ , where a controlling agent bribes voters to
change their preferences (see, e.g., Bartholdi III and Orlin (1991); Bartholdi
III et al. (1989); Conitzer and Sandholm (2006); Faliszewski et al. (2009a,
b)). Control, bribery, and manipulation have been studied for a wide range of
voting rules, as surveyed by Faliszwski and Rothe Faliszewski and Rothe (2016)
(bribery and control) and Conitzer and Walsh Conitzer and Walsh (2016)
(manipulation), see also Baumeister and Rothe (2015).

For Schulze and ranked pairs, Parkes and Xia Parkes and Xia (2012), Xia et al.
Xia et al. (2009), Menton and Singh Menton and Singh (2013), and Gaspers et
al. Gaspers et al. (2013) studied constructive and destructive control by
adding or deleting voters or candidates, bribery, and manipulation. Table 1
gives an overview of known results. Hemaspaandra et al. Hemaspaandra et al.
(2013) showed fixed-parameter tractability for bribing, controlling, and
manipulating Schulze and ranked pairs elections with respect to the number of
candidates and provided algorithms with uniform polynomial running time that
are independent of the number of candidates. Menton and Singh Menton and Singh
(2013) also provided results on control by partition and runoff partition of
candidates and partition of voters for Schulze and further showed some results
for all Condorcet-consistent voting rules.

Table 1: Overview of complexity results for standard control (AC, DC, AV, DV), bribery (B), and manipulation (M) in Schulze and ranked pairs elections. Our results are in blue. Results marked by $\spadesuit$ are due to Parkes and Xia Parkes and Xia (2012); by $\clubsuit$ due to Xia et al. Xia et al. (2009); and by $\blacklozenge$ claimed to be in $\mathrm{P}$ by Menton and Singh Menton and Singh (2012), but later stated as open Menton and Singh (2013) (and omitted from their most recent arXiv version, v4, dated May 24, 2013), and re-established in Theorem 4. $\bigstar$ marks a result by Parkes and Xia Parkes and Xia (2012), extended by Gaspers et al. Gaspers et al. (2013). The original proof of Menton and Singh Menton and Singh (2013) for the result marked by $\diamondsuit$ is corrected in Section 3 and extended to the unique-winner model in Theorem 2. All results, except Schulze-DCDC (where the unique-winner model remains open), hold in both winner models.  | Schulze | Ranked pairs
---|---|---
|  Constructive |  Destructive |  Constructive |  Destructive
AC |  NP-c.♠ |  ? |  NP-c.♠ |  NP-c.♠
DC |  NP-c.♢ |  P◆ |  NP-c.♠ |  NP-c.♠
AV |  NP-c.♠ |  NP-c.♠ |  NP-c.♠ |  NP-c.♠
DV |  NP-c.♠ |  NP-c.♠ |  NP-c.♠ |  NP-c.♠
B |  NP-c.♠ |  NP-c.♠ |  NP-c.♠ |  NP-c.♠
M |  P★ |  P♠ |  NP-c.♣ |  NP-c.♠

##  2 Preliminaries

An election is a pair $(C,V)$, where $C=\\{c_{1},\ldots,c_{m}\\}$ is a set of
candidates and $V$ is a list of $n$ votes in form of preferences over all
candidates in $C$. In this paper, preferences are expressed as a strict linear
order over $C$,333Some voting rule (notably, e.g., Schulze voting Schulze
(2011)) allow voters to express preferences as weak orders. Following previous
work (e.g., Menton and Singh (2013); Parkes and Xia (2012); Hemaspaandra et
al. (2013)), we restrict them here to linear orders. where voters rank the
candidates in descending order from most to least preferred. We write
$c\succ_{v_{i}}d$ to express that a voter $v_{i}\in V$ prefers candidate $c$
over $d$. When it is clear from the context, we omit $\succ_{v_{i}}$ and
simply write $c\,d$. For a set of candidates $A\subseteq C$, we refer to the
lexicographic order (we first consider the alphabetic order and then the
subscript) of those candidates by simply writing $\overrightarrow{A}$, and
$\overleftarrow{A}$ for the reverse. To shorten notation of votes we will
sometimes include sets of candidates in the votes. If a set $A$ occurs in a
vote, the candidates from $A$ are ranked in lexicographic order at the given
place of the voters ranking. For example, $c\,A$ is the same as
$c\,\overrightarrow{A}$ and denotes the vote that ranks $c$ first and then all
candidates from $A$ follow in increasing lexicographic order. For a set of
candidates $C$ and two candidates $c,d\in C$, we will write $W{(c,d)}$ for the
two votes $c\,d\,\overrightarrow{C\setminus\\{c,d\\}}$ and
$\overleftarrow{C\setminus\\{c,d\\}}\,c\,d$. For a given election $(C,V)$, let
$N_{V}{(c,d)}$ be the number of votes, in which candidate $c$ is ranked above
candidate $d$. We call this the pairwise comparison between $c$ and $d$.
Similarly, let $D_{V}{(c,d)}=N_{V}{(c,d)}-N_{V}{(d,c)}$. Note that we omit the
list of votes if it is clear from the context. Before we introduce the
procedures for winner determination in Schulze and ranked pairs election, we
first introduce the weighted majority graph (WMG). A WMG for an election
$(C,V)$ is a weighted directed graph $G=(\hat{V},E,w)$, where $\hat{V}=C$ and
$(c,d)\in E$ with weight $w(c,d)=D_{V}{(c,d)}$ for each ordered pair of
candidates $c,d\in C$. Note that, since the votes are expressed as strict
orders, we have $D_{V}{(c,d)}=-D_{V}{(d,c)}$. Therefore, we omit edges with a
negative weight in depictions.

A voting rule $r:\\{(C,V)\mid(C,V)\text{ is an election}\\}\rightarrow 2^{C}$
determines the set of winners of an election $(C,V)$. We focus on the voting
rules Schulze and ranked pairs. A candidate $c\in C$ is a Condorcet winner of
an election $(C,V)$ if $N_{V}{(c,d)}>N_{V}{(d,c)}$ holds for all $d\in C$ with
$c\neq d$. A candidate $c\in C$ is a weak Condorcet winner if
$N_{V}{(c,d)}\geq N_{V}{(d,c)}$ for all $d\in C$ with $c\neq d$. Note that
there can be at most one Condorcet winner but possibly multiple weak Condorcet
winners. Both Schulze and ranked pairs are _Condorcet-consistent voting rules_
, meaning they choose the Condorcet winner whenever there is one.

### Schulze:

Let the strength of a path $p$ ($\text{str}(p)$) be the weight of the weakest
edge, i.e., the minimum weight, in a directed path $p$ between two candidates
in the WMG. For each distinct pair of candidates $c,d\in C$, let the strength
of the strongest path be $P(c,d)=\max\\{\text{str}(p)\mid\text{$p$ is a path
from $c$ to $d$}\\}$. A candidate $c\in C$ is a Schulze winner of $(C,V)$ if
$P(c,d)\geq P(d,c)$ for each $d\in C\setminus\\{c\\}$. To find these
candidates one can build a second directed graph, which has an edge from $c$
to $d$ if and only if $P(c,d)>P(d,c)$. Each candidate with an in-degree of
zero in this graph is a _Schulze winner_. There can be multiple Schulze
winners.

### Ranked pairs:

For an election $(C,V)$, we first calculate $D_{V}{(c,d)}$ for all distinct
pairs of candidates $c,d\in C$, and order the pairs by weight from highest to
lowest, i.e., we order the values of $D_{V}{(c,d)}$. Now in each step, we
consider the top pair $(c,d)$ of this weight order, which has not yet been
considered. Following Parkes and Xia Parkes and Xia (2012), we break ties
according to a fixed tie-breaking rule. We add an edge $(c,d)$ to a directed
graph $G=(V^{\prime},E)$ where $V^{\prime}=C$, unless inserting this edge
would create a cycle, in which case the pair (edge) is disregarded. When all
pairs have been considered, the _ranked pairs winner of $(C,V)$_ (subject to
the fixed tie-breaking) is the candidate corresponding to the source of
G.444In the original definition, the voting rule ranked pairs Tideman (1987)
returns a complete ranking of the candidates. We use a slightly simplified
definition of ranked pairs introduced by Berker et al. Berker et al. (2022)
that only returns the winner of the election.

For examples of the Schulze and ranked pairs method we refer to the
supplementary material. Note that Tideman Tideman (1987) originally gives an
irresolute procedure and corresponding function for ranked pairs, which
considers all possible ways of breaking ties and is $\mathrm{NP}$-complete
Brill and Fischer (2012). Interestingly, the full ranking of candidates and
winner determination including ties can be computed in polynomial time for
Schulze Schulze (2023). For our reductions, it is important that the
procedures run in polynomial time (which we achieve by using a fixed tie-
breaking scheme for ranked pairs), but it is not necessary to be highly
efficient. Consequently, there may be other procedures that are faster (see,
e.g., Sornat et al. (2021) for Schulze) or handle ties in a different way for
ranked pairs (see, e.g., Brill and Fischer (2012); Wang et al. (2019)).

We study various types of electoral control, starting with constructive
control by deleting candidates (CCDC) which was defined by Bartholdi et al.
Bartholdi III et al. (1992) for a voting rule $\mathcal{E}$:

$\mathcal{E}$-Constructive Control By Deleting Candidates
---
Given: |  An election $(C,V)$, a distinguished candidate $p\in C$, and $\ell\in\mathbb{N}$.
Question: |  Is it possible to make $p$ the unique winner of the $\mathcal{E}$ election resulting from $(C,V)$ by deleting at most $\ell$ candidates?

In the setting of replacing candidates or voters Loreggia et al. (2015);
Erdélyi et al. (2021), the chair must not alter the size of the election and
instead must add a candidate or voter for each one she deletes. Formally, in
$\mathcal{E}$-Constructive Control By Replacing Candidates
($\mathcal{E}$-CCRC) we are given two disjoint sets of candidates, $C$ and
$D$, a list of votes over $C\cup D$, a distinguished candidate $p\in C$, and
$\ell\in\mathbb{N}$, and we ask if it is possible to make $p$ the unique
winner of the $\mathcal{E}$ election resulting from $(C,V)$ by replacing at
most $\ell$ candidates $C^{\prime}\subseteq C$ with candidates
$D^{\prime}\subseteq D$, where $|C^{\prime}|=|D^{\prime}|$.
$\mathcal{E}$-Constructive Control by Replacing Voters ($\mathcal{E}$-CCRV) is
defined analogously by asking whether it is possible to make a preferred
candidate $p$ the unique winner by replacing at most $\ell$ votes
$V^{\prime}\subseteq V$ with votes $U^{\prime}\subseteq U$ such that
$|V^{\prime}|=|U^{\prime}|$, where $U$ is a list of as yet unregistered votes.

In these control scenarios, a chair’s goal is to make a preferred candidate
the unique winner. A chair may also be interested in preventing a candidate
from winning. This setting is known as destructive control Hemaspaandra et al.
(2007). Instead of asking whether a candidate can be made the winner, we ask
whether the sole victory of a candidate can be prevented (note that for a
control action to be successful, it is enough to have the candidate be a
winner among others). We write $\mathcal{E}$-DCDC for
$\mathcal{E}$-Destructive Control by Deleting Candidates, $\mathcal{E}$-DCRC
for $\mathcal{E}$-Destructive Control by Replacing Candidates, and
$\mathcal{E}$-DCRV for $\mathcal{E}$-Destructive Control by Replacing Voters.
Aside from the unique-winner model which is used in the previous definitions,
in the nonunique-winner model we ask whether a preferred candidate can be made
a winner (possibly among others) in the constructive case, and whether a
despised candidate can be prevented from winning altogether in the destructive
case. Note that when interpreting a voting rule as _resolute_ (i.e., to always
yield exactly one winner), the unique-winner and nonunique-winner models are
the same.

In addition to the above control problems, we also study variations of
multimode control as introduced by Faliszewski et al. Faliszewski et al.
(2011), where several of the standard control attacks and bribery can be
combined into one action:

$\mathcal{E}$-Constructive Control By AC+DC+AV+DV+B
---
Given: |  Two disjoint sets of candidates, $C$ and $D$, two disjoint lists of votes over $C\cup D$, $V$ and $U$, a distinguished candidate $p\in C$, and $\ell_{AC}$, $\ell_{DC}$, $\ell_{AV}$, $\ell_{DV}$, $\ell_{B}\in\mathbb{N}$.
Question: |  Is it possible to find two sets, $C^{\prime}\subseteq C\setminus\\{p\\}$ and $D^{\prime}\subseteq D$, and two sublists of votes, $V^{\prime}\subseteq V$ and $U^{\prime}\subseteq U$, such that $p$ is the unique winner of the $\mathcal{E}$ election that results from $((C\setminus C^{\prime})\cup D^{\prime},(V\setminus V^{\prime})\cup U^{\prime})$ by bribing at most $\ell_{B}$ votes in $(V\setminus V^{\prime})\cup U^{\prime})$, and $|D^{\prime}|\leq\ell_{AC}$, $|C^{\prime}|\leq\ell_{DC}$, $|U^{\prime}|\leq\ell_{AV}$, and $|V^{\prime}|\leq\ell_{DV}$?

We abbreviate multimode control problems in the obvious way; e.g., we use the
shorthand $\mathcal{E}$-CCAC+DC+AV+DV+B for the above problem. Faliszewski et
al. Faliszewski et al. (2011) define a method to classify all $2^{5}-1$
variants of multimode control for a voting rule, called classification rule A.
Using the classification rule A and the known results for adding and deleting
candidates or voters and for bribery (see Table 1), it immediately follows
that, except for Schulze-DCAC+DC, Schulze is resistant to any multimode
attack. Since ranked pairs is resistant to all single-pronged attacks, it
clearly also resists all combinations of multimode control.

In any instance of $\mathcal{E}$-Exact Constructive Control by AC+DC+AV+DV+B,
it must hold that $|D^{\prime}|=\ell_{AC}$, $|C^{\prime}|=\ell_{DC}$,
$|U^{\prime}|=\ell_{AV}$, $|V^{\prime}|=\ell_{DV}$, and exactly $\ell_{B}$
voters in $(V\setminus V^{\prime})\cup U^{\prime}$ are bribed. Each
corresponding nonexact control problem polynomial-time Turing reduces to the
exact control problem. The destructive variants $\mathcal{E}$-Destructive
Control by AC+DC+AV+DV+B and $\mathcal{E}$-Exact Destructive Control by
AC+DC+AV+DV+B are defined analogously by asking whether it is possible to make
$p$ not a (unique) winner, and we again use the obvious shorthands. Sometimes,
we exclude certain actions from multimode control, considering, e.g., only
candidate control ($\mathcal{E}$-DCAC+DC) and omit the unneeded input
parameters.

Note that we do not allow candidates in $D$ or voters in $U$ to be deleted, as
we do not consider it realistic to remove a candidate or voter from an
election right after adding. Even though this does not make a difference for
the nonexact problems (as it is allowed to simply add or delete fewer
candidates or voters), it may affect the result for exact multimode control as
shown in the supplementary material.

##  3 Schulze Resists Constructive Control by Deleting Candidates

In this section, we prove the following result by describing and fixing a flaw
in the proof of Menton and Singh Menton and Singh (2013).555Menton and Singh
agree that our construction fixes their flaw. Menton writes (private email
communication on December 5, 2023), _“I have tried my best to understand the
old proof and your correction of it. The diagrams in your paper were very
helpful for this! […] Your solution changes the votes so there are lower
weight edges in the graph and additional paths from $p$ back to the clause
candidates such that there is an equal weight path from $p$ to the clause
candidates to those persisting paths. Deleting the appropriate literal
candidates is still necessary to break the higher-weight paths from the clause
candidates to $p$. Looks good to me!”_

######  Theorem 1.

Schulze-CCDC is $\mathrm{NP}$-complete in the nonunique-winner model.

###### Proof.

The proof of this result, due to Menton and Singh (Menton and Singh, 2013,
Thm. 2.2), shows a clever reduction from $\mathrm{3\textsc{SAT}}$, but it is
technically flawed. We briefly present their reduction and give a
counterexample showing that it is not correct.

In the 3-Satisfiability problem ($\mathrm{3\textsc{SAT}}$), we are given a set
$X$ of variables and a set $Cl=\\{Cl_{1},\ldots,Cl_{k}\\}$ of clauses over
$X$, each having exactly three literals, and we ask whether there is a
satisfying assignment for $\varphi$, where $\varphi$ is the conjunction of all
clauses $Cl_{i}\in Cl$. Given a $\mathrm{3\textsc{SAT}}$ instance $(X,Cl)$,
Menton and Singh Menton and Singh (2013) construct a Schulze-CCDC instance
$((C,V^{\prime}),p,k)$ as follows. The set of candidates $C$ contains $k+1$
clause candidates $c_{i}^{1},\dots,c_{i}^{k+1}$ for each clause $Cl_{i}\in
Cl$, three literal candidates $x_{i}^{1},x_{i}^{2},x_{i}^{3}$ for each clause
$Cl_{i}$, where $x_{i}^{j}$ is the jth literal in clause $Cl_{i}$, $k+1$
negation candidates $n^{1}_{i,j,m,n},\dots,n^{k+1}_{i,j,m,n}$ for each pair of
literals $x_{i}^{j},x_{m}^{n}$, where one is the negation of the other, and
the distinguished candidate $p$ and an additional candidate $a$. Let
$C_{i}=\\{c_{i}^{1},\dots,c_{i}^{k+1}\\}$ be the set of all clause candidates
for clause $Cl_{i}\in Cl$ and let $K=\bigcup_{i=1}^{k+1}C_{i}$ be the set of
all clause candidates. Let $L_{i}=\\{x_{i}^{1},x_{i}^{2},x_{i}^{3}\\}$ be the
set of literal candidates for the clause $Cl_{i}$ and let
$L=\bigcup_{i=1}^{k}L_{i}$ be the set of all literal candidates. Let
$N_{ijmn}=\\{n_{ijmn}^{1},\dots,\ n_{ijmn}^{k+1}\\}$ be the set of negation
candidates for the literals $x_{i}^{j}$, $x_{m}^{n}$ that are a negation of
each other, and let $N$ be the set of all such negation candidates. For a
positive integer $z$, we write $[z]=\\{1,\ldots,z\\}$ as a shorthand.

Menton and Singh Menton and Singh (2013) define the following list of votes
$V^{\prime}$ (which we will change later to fix the proof):

| $\\#$ | preferences |  for each
---|---|---|---
(A) | $1$ | $W{(c_{i}^{j},x_{i}^{1})}$ |  $i\in[k]$, $j\in[k+1]$
(B) | $1$ | $W{(x_{i}^{1},x_{i}^{2})}$ |  $i\in[k]$
(C) | $1$ | $W{(x_{i}^{2},x_{i}^{3})}$ |  $i\in[k]$
(D) | $1$ | $W{(x_{i}^{3},p)}$ |  $i\in[k]$
(E) | $1$ | $W{(a,x)}$ |  $x\in L$
(F) | $1$ | $W{(p,a)}$ |
(G) | $1$ | $W{(x_{i}^{j},n^{l}_{ijmn})}$ |  $l\in[k+1]$ where $x_{m}^{n}$ is the negation of $x_{i}^{j}$
(H) | $1$ | $W{(n,p)}$ |  $n\in N$

The deletion limit is $k$, the number of clauses. Menton and Singh Menton and
Singh (2013) argue that $p$ can be made a Schulze winner by deleting at most
$k$ candidates from $C$ if and only if there is a truth assignment that makes
the given $\mathrm{3\textsc{SAT}}$ instance true.

We now briefly present our counterexample, where we map a yes-instance of
$\mathrm{3\textsc{SAT}}$ to a no-instance of Schulze-CCDC. Let $(X,Cl)$ be our
given $\mathrm{3\textsc{SAT}}$ instance, with $X=\\{x_{1},x_{2},x_{3}\\}$ and
$Cl=\\{(x_{1}\vee x_{2}\vee\neg{x}_{3}),\left(\neg{x}_{1}\vee x_{2}\vee
x_{3}\right)\\}$, i.e., we consider the CNF formula

$\varphi=\left(x_{1}\vee
x_{2}\vee\neg{x}_{3}\right)\wedge\left(\neg{x}_{1}\vee x_{2}\vee
x_{3}\right).$

A detailed description of this counterexample is given in the supplementary
material. Their reduction is quite clever, but unfortunately wrong, as shown
by the counterexample. However, by modifying it appropriately, we can ensure
that $p$ can indeed be made a Schulze winner of the election by deleting at
most $k$ candidates if and only if $(X,Cl)$ is a yes-instance of
$\mathrm{3\textsc{SAT}}$. For our modifications, it is only necessary to
change the list of votes. For votes (A) through (F) we adjust the number of
votes to $2$. Additionally, we add $1$ vote $W(a,c)$ for each $c\in K$.

$a$$p$$c_{1}^{1}$$c_{1}^{2}$$c_{1}^{3}$$c_{2}^{1}$$c_{2}^{2}$$c_{2}^{3}$$x_{1}^{1}$$x_{1}^{2}$$x_{1}^{3}$$x_{2}^{1}$$x_{2}^{2}$$x_{2}^{3}$$n_{1}^{1}$$n_{1}^{2}$$n_{1}^{3}$$n_{2}^{1}$$n_{2}^{2}$$n_{2}^{3}$
Figure 1:  WMG corresponding to the election constructed from the
$\mathrm{3\textsc{SAT}}$ instance from our counterexample with the new
reduction. Dashed edges have weight two and drawn edges have weight four.

The graph in Figure 1 shows the weighted majority graph for the
$\mathrm{3\textsc{SAT}}$ instance from our counterexample adapted to the new
reduction. We claim that $(X,Cl)$ is a yes-instance of
$\mathrm{3\textsc{SAT}}$ if and only if $((C,V),p,k)$ is a yes-instance of
Schulze-CCDC in the nonunique-winner model.

From left to right, let $(X,Cl)$ be a yes-instance of
$\mathrm{3\textsc{SAT}}$. Since we have a yes-instance of
$\mathrm{3\textsc{SAT}}$, we have a truth assignment that makes at least one
literal in each clause $Cl_{i}\in Cl$ true. We claim that $p$ can be made a
Schulze winner by deleting one literal candidate corresponding to some true
literal for each clause. The only path with weight four from a clause
candidate $c_{i}^{j}\in K$ to $p$ is through the literal candidates: from
$x_{i}^{1}$ via $x_{i}^{2}$ to $x_{i}^{3}$. Since we deleted one literal
candidate for each clause, there no longer exists a weight-$4$ path from a
clause candidate to $p$ and $P(p,c)=2\geq P(c,p)$ for $c\in K$. For each $c\in
L\cup\\{a\\}$, we have $P(p,c)=4\geq P(c,p)$. Since we deleted only literal
candidates where the corresponding literal was assigned to be true, we never
have the case that we deleted two literal candidates $x_{i}^{j}$, $x_{m}^{n}$,
which negate each other. Thus we still have a weight-$2$ path from $p$ to each
negation candidate and $P(p,c)=2=P(c,p)$ for each $c\in N$. It follows that
$((C,V),p,k)$ is a yes-instance of Schulze-CCDC in the nonunique-winner model.

From right to left, let $(X,Cl)$ be a no-instance of $\mathrm{3\textsc{SAT}}$.
Thus, for each assignment of the literals, there exists a clause which is
false. To ensure that $p$ is a winner of the election, it is necessary that
$P(p,c)\geq P(c,p)$ for each $c\in C\setminus\\{p\\}$. Since
$P(p,c)=2<4=P(c,p)$ for each $c\in K$, we have to destroy each path of weight
greater than two from the clause candidates to $p$, in particular the path
through the literal candidates $x_{i}^{j}\in C_{i}$, $j\in\\{1,2,3\\}$. Due to
the deletion limit $k=|Cl|$, it is necessary to delete one literal candidate
for each clause. Consider any subset of literals of size $k$ such that for
each clause one literal is contained in the set. It follows that this set
contains at least two literals, $x_{i}^{j}$ and $x_{m}^{n}$, that negate each
other, otherwise, the formula would be satisfiable and we would have a yes-
instance of $\mathrm{3\textsc{SAT}}$. By deleting the corresponding two
literal candidates, we no longer have a path from $p$ to the negation
candidates $n\in N_{ijmn}$. It follows that $P(p,n)<P(n,p)$ and it is
impossible to make $p$ a Schulze winner of the election by deleting at most
$k$ candidates. Therefore, $((C,V),p,k)$ is a no-instance of Schulze-CCDC in
the nonunique-winner model.

From right to left, let $((C,V),p,k)$ be a yes-instance of Schulze-CCDC. To
ensure that $p$ is a winner of the election, it is necessary that $P(p,c)\geq
P(c,p)$ for each $c\in C\setminus\\{p\\}$. Since $P(p,c)=2<4=P(c,p)$ for each
$c\in K$, we have to destroy each path of weight greater than two from the
clause candidates to $p$, in particular the path through the literal
candidates $x_{i}^{j}\in C_{i}$, $j\in\\{1,2,3\\}$. Due to the deletion limit
$k=|Cl|$, it is necessary to delete one literal candidate for each clause.
Consider any subset of literals of size $k$ such that for each clause one
literal is contained in the set. If all of these subsets contained at least
two literals, $x_{i}^{j}$ and $x_{m}^{n}$, that negate each other, i.e., if
the $\mathrm{3\textsc{SAT}}$ formula were not satisfiable, by deleting the
corresponding two literal candidates, we would no longer have a path from $p$
to the negation candidates $n\in N_{ijmn}$. That is, it would hold that
$P(p,n)<P(n,p)$ and it would be impossible to make $p$ a Schulze winner by
deleting at most $k$ candidates. Thus, since we have a yes-instance of
Schulze-CCDC, there must exist at least one subset of literals, such that for
each clause one literal is contained in the set, i.e., set to true and we have
$\mathrm{3\textsc{SAT}}$-yes.

Finally, it is easy to see that Schulze-CCDC is in $\mathrm{NP}$. ∎

Previously, Schulze-CCDC was only studied in the nonunique-winner model. By
slightly adapting the previous construction (see the supplementary material),
we can now also show $\mathrm{NP}$-completeness in the unique-winner model.

######  Theorem 2.

Schulze-CCDC is $\mathrm{NP}$-complete in the unique-winner model.

##  4 Destructive Control by Deleting Candidates and Variants Thereof

In this section, we examine a peculiarity of standard destructive control by
deleting candidates for Schulze elections, which allows us to reduce the
number of candidates we need to consider for deletion. Using this approach, we
are able to re-establish the result that DCDC is polynomial-time solvable for
Schulze elections, which Menton and Singh claimed in an early version (v1) of
their arXiv preprint Menton and Singh (2012). However, Menton and Singh
removed this result (and the corresponding result for Schulze-DCAC) from all
subsequent versions of the arXiv preprint and from their IJCAI 2013 paper
Menton and Singh (2013), stating these two control problems as open.
Additionally, we consider the relationship of variations of destructive
control by deleting candidates to variations of $s$-$t$ vertex cut. All
omitted proofs can be found in the supplementary material.

We first introduce a variant of _$s$ -$t$ vertex cut_ defined by Menton and
Singh Menton and Singh (2013): Path-Preserving Vertex Cut. Recall that for
destructive control in Schulze elections to be successful, one candidate must
be boosted to beat the despised candidate and that by deleting candidates we
can only lower the strength of the strongest path but can never increase it.
Hence, we need to cut paths such that the best remaining path to the despised
candidate is stronger than all paths from the despised to our chosen boosted
candidate. Menton and Singh Menton and Singh (2013) capture this notion of
_path-preserving vertex cut_ by defining the problem as essentially asking
whether there exists an $s$-$t$ vertex cut (destroying the stronger paths from
$s$ to $t$) of size at most $k$, while at least one path from $t$ to $s$ must
remain intact. When searching for candidates to delete to boost some candidate
to beat the despised candidate, it is useful if we can reduce the search
space. We will at times refer to these candidates as _rivals of the despised
candidate_. For the standard control problem we show that this is indeed
possible and the chair can limit the search to the in-neighborhood of the
boosted candidate.

######  Theorem 3.

If destructive control by deleting candidates is possible for a given Schulze
election, then there exists some candidate $c\in C$ who can beat the despised
candidate $w$ by only deleting candidates who directly beat $c$ (i.e., are in-
neighbors of $c$ in the WMG).666This result can be extended to any pair of
candidates $c,w\in C$ where $P(w,c)\geq P(c,w)$ and we have a yes-instance of
Path-Preserving Vertex Cut for the graph induced by the paths between these
two candidates.

###### Proof.

Let $c\in C$ be some candidate where $P(w,c)\geq P(c,w)$, i.e., $w$ has a
stronger (or equally strong) path to $c$ than the other way round. Assume that
$c$ can beat $w$ by deleting the minimal number of candidates needed (with
regards to the number necessary for making other candidates beat $w$). We
claim that either those deleted candidates are direct neighbors of $c$, or
there exists some other candidate $c^{*}\in C$ for which we can reach the same
goal by deleting equally many or even fewer candidates in the neighborhood of
$c^{*}$.

First, we define some notation. Let $Del^{c}_{w}$ be the minimal number of
removed candidates needed to make $c$ beat $w$. Note that these candidates
form a path-preserving vertex cut. We say that $x$ is before $z$ if $x$ is
closer to $w$ than $z$. Let $N^{+}(c)$ be the in-neighborhood of a candidate
$c$, i.e., $N^{+}(c)$ contains all candidates with a direct edge to $c$.
Finally, we define $Ind^{c}_{w}$ as the candidates belonging to the connected
component of $c$ as induced by the vertex cut $Del^{c}_{w}$. Intuitively,
$Ind^{c}_{w}$ contains all candidates on stronger paths from $w$ to $c$ that
are broken by deleting candidates and where the cut is before the candidate.

Clearly, any $z^{*}\in Ind^{c}_{w}$ also beats $w$ as first $P(z^{*},c)\geq
P(c,w)$ and thus $P(z^{*},w)\geq P(c,w)$, and secondly, no path from $w$ to
$z^{*}$ with strength greater than $P(c,w)$ can exist. It follows that $\lvert
Del^{z^{*}}_{w}\rvert\leq\lvert Del^{c}_{w}\rvert$. We distinguish two cases.

Case 1:

$Ind^{c}_{w}=\emptyset$. Since $Del^{c}_{w}$ is a minimal cut, we have
$Del^{c}_{w}\subseteq N^{+}(c)$.

Case 2:

$Ind^{c}_{w}\neq\emptyset$. Let $F=\\{f\in Ind^{c}_{w}\mid N^{+}(f)\cap
Del^{c}_{w}\neq\emptyset\\}$ be the set of all candidates in the connected
component of $c$, where we deleted some candidates in the in-neighborhood of
$c$. On the one hand, if $\lvert F\rvert=1$ we have a candidate $f\in F$ who
also beats $w$ by deleting $Del^{c}_{w}$. Since $Del^{c}_{w}$ is minimal, it
follows that $Del^{f}_{w}=Del^{c}_{w}$, and therefore, for a successful
control action against $w$, it suffices to delete from $N^{+}(f)$. On the
other hand, if $\lvert F\rvert>1$, then $N^{+}(f)\cap Del^{c}_{w}=N^{+}(g)\cap
Del^{c}_{w}$ for all $f,g\in F$. For a contradiction, assume there are two
candidates $f,g\in F$ who do not share the same in-neighbors in $Del^{c}_{w}$.
Deleting either $N^{+}(f)\cap Del^{c}_{w}$ or $N^{+}(g)\cap Del^{c}_{w}$ is
sufficient to make the respective candidate beat $w$. Since $N^{+}(f)\cap
Del^{c}_{w}\neq N^{+}(g)\cap Del^{c}_{w}$, we have a contradiction to
$Del^{c}_{w}$ being minimal.∎

This result can be used to design an algorithm for Schulze-DCDC in the
nonunique-winner model, which runs in polynomial time. Unfortunately, we
cannot easily transfer our algorithm to work in the unique-winner model. The
complete algorithm, proof of correctness (based on Theorem 3) and further
explanation as well as an example of why the algorithm cannot solve the
unique-winner model can be found in the supplementary material. Intuitively,
for a despised candidate $d$, the algorithm works by considering every
candidate $c\in C\setminus\\{d\\}$ as a possible rival of $d$ and testing
whether $c$ is successful by considering the part of the in-neighborhood of
$c$ that intersects the stronger paths from $d$ to $c$ for deletion.

######  Theorem 4.

In the nonunique-winner model, Schulze-DCDC is solvable in polynomial time.

For variants of destructive control, we need to encode the restriction, which
is imposed on the deletion set, into the vertex cut, essentially creating
corresponding new Path-Preserving Vertex Cut decision problems. There are
several natural restrictions one may apply to Schulze-DCDC, e.g., some
candidates may be protected from deletion or labeled candidates must be
deleted together. We give examples and prove the relationship to vertex cut
for some of these variants in the supplementary material.

##  5 Exact Multimode Control and Control by Replacing

Now we turn to exact multimode control and control by replacing candidates or
voters. In the former control type, the chair must adhere to alter an _exact_
number of candidates or voters or both. In the latter, the chair must add the
_same_ number of either candidates or voters as previously have been deleted,
i.e., must replace them. Lorregia et al. Loreggia et al. (2015) showed that
any voting rule that is resistant to constructive control by deleting
candidates and satisfies _insensitivity to bottom-ranked candidates (IBC)_
Lang et al. (2013) is also resistant to constructive control by replacing
candidates. A voting rule $\mathcal{E}$ is said to be _insensitive to bottom-
ranked candidates_ if, given an election $(C,V)$ and a new candidate $x$, the
elections $(C,V)$ and $(C\cup\\{x\\},V^{x})$, where $V^{x}$ is the list of
votes obtained by adding $x$ as the least preferred alternative to each vote
in $V$, have the same winners under $\mathcal{E}$. We extend their result to
also apply to $\mathcal{E}$-ECCAC+DC and $\mathcal{E}$-ECCRC.

Table 2 provides an overview of our results. All (full) proofs omitted in this
section can be found in the supplementary material.

Table 2:  Overview of complexity results for exact multimode control and control by replacing in both winner models. Results marked by ♠ can be found in Corollary 2, by ♡ in Corollary 3, by ♢ in Corollary 1, by ⋆ in Theorem 5 and by ∘ in Theorem 6.  | Schulze | Ranked pairs
---|---|---
|  Const. |  Destr. |  Constr. |  Destr.
ExactCAC+DC |  NP-c.♠ |  ? |  NP-c.♠ |  NP-c.♡
ExactCRC |  NP-c.♠ |  ? |  NP-c.♠ |  NP-c.♡
ExactCRC |  NP-c.♢ |  ? |  NP-c.♢ |  NP-c.♡
ExactCAV+DV |  NP-c.⋆ |  NP-c.⋆ |  NP-c.∘ |  NP-c.∘
ExactCRV |  NP-c.⋆ |  NP-c.⋆ |  NP-c.∘ |  NP-c.∘

######  Lemma 1.

Let $\mathcal{E}$ be a voting rule that satisfies IBC. In both the unique- and
nonunique-winner model, if $\mathcal{E}$-CCDC is $\mathrm{NP}$-hard, then so
are $\mathcal{E}$-ECCAC+DC and $\mathcal{E}$-ECCRC.

###### Proof.

We reduce $\mathcal{E}$-CCDC to $\mathcal{E}$-ECCAC+DC and
$\mathcal{E}$-ECCRC. Let $(C,V,p,k)$ be an instance of $\mathcal{E}$-CCDC.
Define $C^{\prime}=C\cup X$ with $X=\\{x_{1},\ldots,x_{k}\\}$,
$D=\\{d_{1},\ldots,d_{\ell_{AC}}\\}$, $\ell_{DC}=\ell_{RC}=k$, and set
$\ell_{AC}\in\mathbb{N}$ arbitrarily. Let $V^{\prime}=v\,X\,D$ for every $v\in
V$, i.e., add all candidates from $X$ at the bottom of every vote and then add
all candidates from $D$ at the bottom of those votes. Construct an instance
$(C^{\prime},D,V^{\prime},p,\ell_{AC},\ell_{DC})$ of $\mathcal{E}$-ECCAC+DC
and an instance $((C^{\prime},V^{\prime}),p,\ell_{RC})$ of
$\mathcal{E}$-ECCRC.

Assume we have a yes-instance of $\mathcal{E}$-CCDC. Then there exists a set
$C^{d}\subset C$ with $|C^{d}|\leq\ell_{DC}$ such that $p$ wins the election
$(C\setminus C^{d},V)$. Delete all candidates in $C^{d}$ and some candidates
in $X^{d}\subseteq X$ such that exactly $\ell_{DC}$ candidates were deleted
and add $\ell_{AC}$ arbitrary candidates $D^{a}\subseteq D$ to the election.
Since $\mathcal{E}$ is IBC, candidate $p$ is a winner of the election
$(C^{\prime}\cup D^{a}\setminus(C^{d}\cup X^{d}),V^{\prime})$ and
$\mathcal{E}$-ECCAC+DC is also a yes-instance.

Now assume, we have a no-instance of $\mathcal{E}$-CCDC. Then there is no set
$C^{d}\subset C$ with $|C^{d}|\leq k$ such that $p$ wins the election
$(C\setminus C^{d},V)$. Since $\mathcal{E}$ is IBC, deleting any set of
candidates from $X$ or adding any candidate from $D$ has no influence on the
winners of the election. Thus, to make $p$ an $\mathcal{E}$ winner, we need to
find a set of at most $\ell_{DC}$ candidates in $C$ to delete, which is
impossible as $\mathcal{E}$-CCDC is a no-instance.

The argument for $\mathcal{E}$-ECCRC is analogous. ∎

######  Lemma 2.

Let $\mathcal{E}$ be a voting rule that satisfies IBC. In both the unique- and
nonunique-winner model, if $\mathcal{E}$-DCDC is $\mathrm{NP}$-hard, then so
are $\mathcal{E}$-EDCAC+DC and $\mathcal{E}$-EDCRC.

The same construction and proof idea used in the proof of Lemma 1 works for
Lemma 2 as well.

######  Lemma 3.

Schulze and ranked pairs are insensitive to bottom-ranked candidates.

######  Corollary 1.

In both the unique- and nonunique-winner model, Schulze-CCRC and Ranked-Pairs-
CCRC are $\mathrm{NP}$-complete.

######  Corollary 2.

In both the unique- and nonunique-winner model, Schulze-ECCAC+DC, Schulze-
ECCRC, Ranked-Pairs-ECCAC+DC, and Ranked-Pairs-ECCRC are
$\mathrm{NP}$-complete.

######  Corollary 3.

In both the unique- and nonunique-winner model, Ranked-Pairs-EDCAC+DC, Ranked-
Pairs-EDCRC, and Ranked-Pairs-DCRC are $\mathrm{NP}$-complete.

Schulze and ranked pairs are equally resistant to all constructive and
destructive control actions of the voter list considered in this paper.

######  Theorem 5.

In both the unique- and nonunique-winner model, Schulze-ECCAV+DV, Schulze-
CCRV, Schulze-EDCAV+DV, and Schulze-DCRV are $\mathrm{NP}$-complete.

Proof sketch. We reduce from Restricted Exact Cover By 3-Sets (RX3C) Gonzalez
(1985): Given a set $B=\\{b_{1},\ldots,b_{3s}\\}$ with $s\geq 1$ and a list
$\mathcal{S}=\\{S_{1},\ldots,S_{3s}\\}$, where
$S_{i}=\\{b_{i,1},b_{i,2},b_{i,3}\\}$ and $S_{i}\subseteq B$ for all
$S_{i}\in\mathcal{S}$ and each $b_{j}$ is contained in exactly three sets
$S_{i}\in\mathcal{S}$, does there exist an exact cover, i.e., a sublist
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such that each $b_{i}\in B$ occurs
in exactly one $S_{i}\in\mathcal{S}^{\prime}$?

Let $\ell_{AV}=\ell_{DV}=s$ for the Schulze-ECCAV+DV and Schulze-EDCAV+DV
instances we construct, and let $\ell_{RV}=s$ for the Schulze-CCRV and
Schulze-DCRV instances. Further, let $\mathcal{L}\gg s$ be a constant much
greater than $s$.777The precise value of $\mathcal{L}$ is not important; all
that matters is that when used as an edge weight in a WMG, $\mathcal{L}$ is
large enough, such that any edge changed by the control actions must not
change in direction, i.e., the sign of the edge weight must not flip. Recall
that the strength of a path in a WMG is specified as the weight of the weakest
edge on the path. From $(B,\mathcal{S})$ we construct an election $(C,V)$ as
depicted in Figure 2. Note that candidate $w$ is the unique winner of the
election.

$b_{2}$$b_{1}$$\ldots$$b_{3s}$$p$$w$$\gg 2\mathcal{L}$$\gg 2\mathcal{L}$$\gg
2\mathcal{L}$$2\mathcal{L}$pt$2\mathcal{L}+2\ell_{DV}$$+2\ell_{AV}-2$pt$2\mathcal{L}+2\ell_{DV}$$+2\ell_{AV}-2$$2\mathcal{L}+2\ell_{DV}+2\ell_{AV}-2$
Figure 2: The WMG of the election from the proof of Theorem 5.

The list of additional votes $U$ contains one vote

$S_{i}\,p\,(B\setminus S_{i})\,w\hskip 14.22636pt\text{for each}\
S_{i}\in\mathcal{S}.$

Let $p$ be the distinguished candidate for the constructive case and $w$ be
the despised candidate for the destructive case.

By adapting the above construction, we obtain the same results for ranked
pairs.

######  Theorem 6.

In both the unique- and nonunique-winner model, Ranked-Pairs-ECCAV+DV, Ranked-
Pairs-CCRV, Ranked-Pairs-EDCAV+DV, and Ranked-Pairs-DCRV are
$\mathrm{NP}$-complete.

##  6 Conclusion and Future Work

We have studied electoral control for Schulze and ranked pairs elections:
After fixing a flaw in the proof of Menton and Singh (Menton and Singh, 2013,
Theorem 2.2) for Schulze-CCDC and extending the new construction to the
unique-winner model (Section 3), we study variants of $s$-$t$ vertex cuts in
graphs that are related to destructive control by deleting candidates in
Schulze elections, and re-establish a vulnerability result on the
corresponding problem (Section 4). Finally, in Section 5, we established a
number of resistance results for control by replacing candidates or voters and
exact multimode control. Hence, our work establishes both polynomial-time
algorithms and $\mathrm{NP}$-completeness results. Tables 1 and 2 provide a
summary of our results in the context of related known results.

However, multiple variants of destructive control of the candidate set (see
Section 4), such as destructive control by adding candidates both in the
unique- and nonunique-winner model and by deleting candidates in the unique-
winner model, remain open for Schulze elections. Lastly, to the best of our
knowledge, most cases of control by partition are yet to be solved for ranked
pairs elections.

## Ethical Statement

The subject of this paper—electoral control—is an ethically sensitive topic.
The goal of our work is not to help strategic parties to control elections but
to ‘audit’ some voting rules with respect to their vulnerability to electoral
control. In particular, our resistance results are clearly helpful to society
since they may help protect society from attacks against elections, and our
vulnerability results are clearly helpful to society since they can be used to
avoid voting rules that are vulnerable to certain types of electoral control
that realistically may occur in the context of an election. Hence, the purpose
of our research is to provide detailed information on the societal impact of
voting rules and to ensure transparency.

## Acknowledgments

We are grateful to Ulle Endriss, Piotr Faliszewski, Edith Hemaspaandra, Lane
A. Hemaspaandra, and Jérôme Lang for their ethical advice. We thank the
anonymous reviewers for helpful comments. This work was supported in part by
DFG research grant RO-1202/21-1.

## References

  * Bartholdi III and Orlin [1991] John J. Bartholdi III and James B. Orlin.  Single transferable vote resists strategic voting.  Social Choice and Welfare, 8(4):341–354, 1991.
  * Bartholdi III et al. [1989] John J. Bartholdi III, Craig Tovey, and Michael Trick.  The computational difficulty of manipulating an election.  Social Choice and Welfare, 6(3):227–241, 1989.
  * Bartholdi III et al. [1992] John J. Bartholdi III, Craig Tovey, and Michael Trick.  How hard is it to control an election?  Mathematical and Computer Modelling, 16(8/9):27–40, 1992.
  * Baumeister and Rothe [2015] Dorothea Baumeister and Jörg Rothe.  Preference aggregation by voting.  In Jörg Rothe, editor, Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, Springer Texts in Business and Economics, chapter 4, pages 197–325. Springer-Verlag, Heidelberg and Berlin, Germany, 2015.
  * Baumeister et al. [2020] Dorothea Baumeister, Gábor Erdélyi, Olivia Erdélyi, Jörg Rothe, and Ann-Kathrin Selker.  Complexity of control in judgment aggregation for uniform premise-based quota rules.  Journal of Computer and System Sciences, 112:13–33, 2020.
  * Berker et al. [2022] Ratip Emin Berker, Sílvia Casacuberta, Christopher Ong, and Isaac Robinson.  Obvious independence of clones.  Technical Report arXiv:2210.04880v1 [cs.GT], ACM Computing Research Repository (CoRR), October 2022.
  * Brill and Fischer [2012] Markus Brill and Felix Fischer.  The price of neutrality for the ranked pairs method.  In Proceedings of the 26th AAAI Conference on Artificial Intelligence, pages 1299–1305. AAAI Press, July 2012.
  * Conitzer and Sandholm [2006] Vincent Conitzer and Tuomas Sandholm.  Nonexistence of voting rules that are usually hard to manipulate.  In Proceedings of the 21st National Conference on Artificial Intelligence, pages 627–634. AAAI Press, July 2006.
  * Conitzer and Walsh [2016] Vincent Conitzer and Toby Walsh.  Barriers to manipulation in voting.  In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 6, pages 127–145. Cambridge University Press, Cambridge, UK, 2016.
  * Conitzer et al. [2009] Vincent Conitzer, Matthew Rognlie, and Lirong Xia.  Preference functions that score rankings and maximum likelihood estimation.  In Proceedings of the 21st International Joint Conference on Artificial Intelligence, pages 109–115. IJCAI, July 2009.
  * Erdélyi et al. [2015] Gábor Erdélyi, Edith Hemaspaandra, and Lane A. Hemaspaandra.  More natural models of electoral control by partition.  In Proceedings of the 4th International Conference on Algorithmic Decision Theory, pages 396–413, Heidelberg and Berlin, Germany, September 2015. Springer-Verlag Lecture Notes in Artificial Intelligence #9346.
  * Erdélyi et al. [2021] Gábor Erdélyi, Marc Neveling, Christian Reger, Jörg Rothe, Yongjie Yang, and Roman Zorn.  Towards completing the puzzle: Complexity of control by replacing, adding, and deleting candidates or voters.  Journal of Autonomous Agents and Multi-Agent Systems, 35(2):41:1–41:48, 2021.
  * Faliszewski and Rothe [2016] Piotr Faliszewski and Jörg Rothe.  Control and bribery in voting.  In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 7, pages 146–168. Cambridge University Press, Cambridge, UK, 2016.
  * Faliszewski et al. [2009a] Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra.  How hard is bribery in elections?  Journal of Artificial Intelligence Research, 35:485–532, 2009.
  * Faliszewski et al. [2009b] Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe.  Llull and Copeland voting computationally resist bribery and constructive control.  Journal of Artificial Intelligence Research, 35:275–341, 2009.
  * Faliszewski et al. [2011] Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra.  Multimode control attacks on elections.  Journal of Artificial Intelligence Research, 40:305–351, 2011.
  * Gaspers et al. [2013] Serge Gaspers, Thomas Kalinowski, Nina Narodytska, and Toby Walsh.  Coalitional manipulation for Schulze’s rule.  In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, pages 431–438. IFAAMAS, May 2013.
  * Gonzalez [1985] Teofilo F. Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical Computer Science, 38:293–306, 1985.
  * Hemaspaandra et al. [2007] Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe.  Anyone but him: The complexity of precluding an alternative.  Artificial Intelligence, 171(5–6):255–285, 2007.
  * Hemaspaandra et al. [2013] Lane A. Hemaspaandra, Rahman Lavaee, and Curtis Menton.  Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control.  In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, pages 1345–1346. IFAAMAS, May 2013\.
  * Kaczmarek and Rothe [2024] Joanna Kaczmarek and Jörg Rothe.  Controlling weighted voting games by deleting or adding players with or without changing the quota.  Annals of Mathematics and Artificial Intelligence, 2024.  In print. DOI: https://doi.org/10.1007/s10472-023-09874-x.
  * Kaczmarek et al. [2023] Joanna Kaczmarek, Jörg Rothe, and Nimrod Talmon.  Complexity of control by adding or deleting edges in graph-restricted weighted voting games.  In Proceedings of the 26th European Conference on Artificial Intelligence, volume 372 of Frontiers in Artificial Intelligence and Applications, pages 1190–1197. IOS Press, October 2023.
  * Lang et al. [2013] Jérôme Lang, Nicolas Maudet, and Maria Polukarov.  New results on equilibria in strategic candidacy.  In Proceedings of the 6th International Symposium on Algorithmic Game Theory, pages 13–25. Springer-Verlag Lecture Notes in Computer Science #8146, October 2013.
  * Loreggia et al. [2015] Andrea Loreggia, Nina Narodytska, Francesca Rossi, Kristen Brent Venable, and Toby Walsh.  Controlling elections by replacing candidates or votes (extended abstract).  In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, pages 1737–1738. IFAAMAS, May 2015\.
  * McGarvey [1953] David C. McGarvey.  A theorem on the construction of voting paradoxes.  Econometrica, 21(4):608–610, 1953.
  * Menton and Singh [2012] Curtis Menton and Preetjot Singh.  Manipulation and control complexity of Schulze voting.  Technical Report arXiv:1206.2111v1 [cs.GT], ACM Computing Research Repository (CoRR), June 2012.
  * Menton and Singh [2013] Curtis Menton and Preetjot Singh.  Control complexity of Schulze voting.  In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pages 286–292. AAAI Press/IJCAI, August 2013.
  * Parkes and Xia [2012] David Parkes and Lirong Xia.  A complexity-of-strategic-behavior comparison between Schulze’s rule and ranked pairs.  In Proceedings of the 26th AAAI Conference on Artificial Intelligence, pages 1429–1435. AAAI Press, July 2012.
  * Rey and Rothe [2018] Anja Rey and Jörg Rothe.  Structural control in weighted voting games.  The B.E. Journal on Theoretical Economics, 18(2):1–15, 2018.
  * Schulze [2011] Markus Schulze.  A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method.  Social Choice and Welfare, 36(2):267–303, 2011.
  * Schulze [2023] Markus Schulze.  The Schulze method of voting.  Technical Report arXiv:1804.02973v13 [cs.GT], ACM Computing Research Repository (CoRR), May 2023.
  * Sornat et al. [2021] Krzysztof Sornat, Virginia Vassilevska Williams, and Yinzhan Xu.  Fine-grained complexity and algorithms for the schulze voting method.  In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 841–859. ACM Press, July 2021.
  * Tideman [1987] T. Nicolaus Tideman.  Independence of clones as a criterion for voting rules.  Social Choice and Welfare, 4(3):185–206, 1987.
  * Wang et al. [2019] Jun Wang, Sujoy Sikdar, Tyler Shepherd, Zhibing Zhao, Chunheng Jiang, and Lirong Xia.  Practical algorithms for multi-stage voting rules with parallel universes tiebreaking.  In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 2189–2196. AAAI Press, January/February 2019.
  * West [2017] Douglas B. West.  Introduction to Graph Theory.  Pearson, Cham, Switzerland, 2 edition, 2017.
  * Xia et al. [2009] Lirong Xia, Michael Zuckerman, Ariel D. Procaccia, Vincent Conitzer, and Jeffrey S. Rosenschein.  Complexity of unweighted coalitional manipulation under some common voting rules.  In Proceedings of the 21st International Joint Conference on Artificial Intelligence, pages 348–353. IJCAI, July 2009.

##  Appendix A Deferred Example from Section 1

######  Example 1.

The following simple example illustrates the difference between the exact and
non exact versions of electoral control. Given an election $(\\{p,d\\},V)$ and
unregistered candidates $D=\\{a,b\\}$. The pairwise comparisons are
illustrated in Figure 6. Clearly, $d$ wins in the original election. Consider
constructive control by adding candidates where $k=2$ and candidate $p$ is the
preferred winner. For non exact control a chair may add $a$, which $p$ beats
directly and this also introduces a stronger path from $p$ to $d$, making $p$
the unique winner of the election. However, should the chair also add $b$, the
successful control action is immediately reversed, as $b$ beats $p$ in the
pairwise contest. Thus, exact control is not possible in this setting.

$d$$a$$b$$p$$2$$4$$4$$6$$6$ Figure 3: A WMG of the election in Example 1.
Candidates from the set of unregistered candidates $D$ are depicted using
dashed lines.

##  Appendix B Deferred Example from Section 2

######  Example 2.

Consider an election $(C,V)$ with $C=\\{a,b,c,d\\}$ and the following votes:

$\displaystyle 4\times v_{1}:\ a\ c\ b\ d,$ $\displaystyle 2\times v_{2}:\ d\
a\ c\ b,$ $\displaystyle 3\times v_{3}:\ d\ c\ a\ b,$ $\displaystyle 2\times
v_{4}:\ b\ d\ a\ c.$

First, we determine $N_{V}{(x,y)}$ for each pair of candidates $x,y\in C$ to
build the WMG:

$\displaystyle N_{V}{(a,b)}=9,$ $\displaystyle N_{V}{(a,c)}=8,\hskip
20.00003pt$ $\displaystyle N_{V}{(a,d)}=4,$ $\displaystyle N_{V}{(b,a)}=2,$
$\displaystyle N_{V}{(b,c)}=2,\hskip 20.00003pt$ $\displaystyle
N_{V}{(b,d)}=6,$ $\displaystyle N_{V}{(c,a)}=3,$ $\displaystyle
N_{V}{(c,b)}=9,\hskip 20.00003pt$ $\displaystyle N_{V}{(c,d)}=4,$
$\displaystyle N_{V}{(d,a)}=7,$ $\displaystyle N_{V}{(d,b)}=5,\hskip
20.00003pt$ $\displaystyle N_{V}{(d,c)}=7.$

The WMG is shown in Figure 4. The strengths of the strongest paths for each
pair of candidates $x,y\in C$ are given in Table 3. Since $P(d,x)>P(x,d)$ for
each $x\in C\setminus\\{d\\}$, candidate $d$ is the unique Schulze winner of
the election.

abcd$7$$5$$1$$7$$3$$3$ Figure 4: Weighted majority graph in Example 2.

$P{(x,y)}$ |  $a$ |  $b$ |  $c$ |  $d$
---|---|---|---|---
$a$ |  – |  $\mathbf{7}$ |  $\mathbf{5}$ |  $1$
$b$ |  $1$ |  – |  $1$ |  $1$
$c$ |  $1$ |  $\mathbf{7}$ |  – |  $1$
$d$ |  $\mathbf{3}$ |  $\mathbf{3}$ |  $\mathbf{3}$ |  –

Table 3: Strengths of the strongest paths in Example 2. Bold font indicates
$P(x,y)\geq P(y,x)$.

######  Example 3.

Consider the election described in Example 2. By using lexicographical, i.e.,
here alphabetical, tie-breaking, we get the weight order shown in Table 4. We
now start by considering the first pair $(a,b)$. The corresponding edge
$(a,b)$ can of course be inserted into the directed graph $G$. In the next
four steps, one after another we consider the pairs (or, edges) $(c,b)$,
$(a,c)$, $(d,a)$, and $(d,c)$, which can all be added to $G$ since none of
them creates a cycle. Only the last edge $(b,d)$ cannot be inserted since we
would then get a cycle among $b$, $c$, and $d$. The directed graph $G$ is
depicted in Figure 5. Being the source of the graph, $d$ is the ranked pairs
winner of the election.

|  pair $(c_{i},c_{j})$ | $D_{V}{(c_{i},c_{j})}$
---|---|---
1. | $(a,b)$ | $7$
2. | $(c,b)$ | $7$
3. | $(a,c)$ | $5$
4. | $(d,a)$ | $3$
5. | $(d,c)$ | $3$
6. | $(b,d)$ | $1$

Table 4: Candidate pairs ordered by difference in pairwise comparison in
Example 3.

abcd Figure 5: Directed graph $G$ in Example 3.

######  Example 4.

Consider a Schulze election where apart from the preferred candidate $p$ and
the current winner $w$ only two more candidates, $c_{1}$ and $c_{2}$, are
present. Let the election have one stronger path from $w$ to $p$ through
$c_{1}$ and one weaker path from $p$ to $w$ through $c_{2}$. The set $D$ of as
yet unregistered candidates to be added contains only $d$, who is on a path
from $w$ to $p$ that is as strong as the path from $w$ to $p$ through $c_{1}$.
This scenario is illustrated in Figure 6. Let $\ell_{DC}=2$ and $\ell_{AC}=1$.
If we do not allow deletion of recently added candidates, we are forced to
delete both candidates $c_{1}$ and $c_{2}$ in any exact control action and to
add the one candidate from $D$. But this would make it impossible for $p$ to
win. However, if we are allowed to delete $d$ after adding (thus in effect
reducing both $\ell_{DC}$ and $\ell_{AC}$ by one), our control action—first
adding $d$ and then deleting $c_{1}$ and $d$—is successful.

$w$$c_{1}$$d$$p$$c_{2}$$4$$4$$4$$4$$2$$2$ Figure 6: A WMG of the election in
Example 4, illustrating that it may be necessary to delete recently added
candidates for an exact control action to be successful.

##  Appendix C Deferred Counterexample and Proof of Section 3

######  Example 5.

We start with a yes-instance of $\mathrm{3\textsc{SAT}}$, which will be mapped
to a no-instance of Schulze-CCDC by their reduction. Let $(X,Cl)$ be our given
$\mathrm{3\textsc{SAT}}$ instance, with $X=\\{x_{1},x_{2},x_{3}\\}$ and
$Cl=\\{(x_{1}\vee x_{2}\vee\neg{x}_{3}),\left(\neg{x}_{1}\vee x_{2}\vee
x_{3}\right)\\}$, i.e., we consider the CNF formula

$\varphi=\left(x_{1}\vee
x_{2}\vee\neg{x}_{3}\right)\wedge\left(\neg{x}_{1}\vee x_{2}\vee
x_{3}\right).$

According to the proof of [Menton and Singh, 2013, Thm. 2.2], we construct an
instance $((C,V^{\prime}),p,\ell)$ of Schulze-CCDC as follows. The deletion
limit is $k=2$, the number of clauses $|Cl|$. The set of candidates, $C=K\cup
L\cup N\cup\\{p,a\\}$, consists of

  * •

the clause candidates $c_{1}^{1}$, $c_{1}^{2}$, $c_{1}^{3},c_{2}^{1}$,
$c_{2}^{2}$, and $c_{2}^{3}$,

  * •

the literal candidates $x_{1}^{1}$, $x_{1}^{2}$, $x_{1}^{3}$, $x_{2}^{1}$,
$x_{2}^{2}$, and $x_{2}^{3}$,

  * •

the negation candidates $n_{1,1,2,1}^{1}$, $n_{1,1,2,1}^{2}$,
$n_{1,1,2,1}^{3}$, $n_{1,3,2,3}^{1}$, $\ n_{1,3,2,3}^{2}$, and
$n_{1,3,2,3}^{3}$ (abbreviate by $n_{1}^{1}$, $n_{1}^{2}$, $n_{1}^{3}$,
$n_{2}^{1}$, $n_{2}^{2}$, and $n_{2}^{3}$),

  * •

the distinguished candidate $p$ and the additional candidate $a$.

The preferences are represented by the WMG in Figure 7 using McGarvey’s trick
McGarvey [1953]. Each edge in this graph has a weight of two.

ap$c_{1}^{1}$$c_{1}^{2}$$c_{1}^{3}$$c_{2}^{1}$$c_{2}^{2}$$c_{2}^{3}$$x_{1}^{1}$$x_{1}^{2}$$x_{1}^{3}$$x_{2}^{1}$$x_{2}^{2}$$x_{2}^{3}$$n_{1}^{1}$$n_{1}^{2}$$n_{1}^{3}$$n_{2}^{1}$$n_{2}^{2}$$n_{2}^{3}$
Figure 7: Weighted majority graph corresponding to the election
$(C,V^{\prime})$ constructed from a 3SAT instance in Example 5. All edges have
a weight of two.

Before control, every clause candidate $c_{i}^{j}$, with $i\in[2]$ and
$j\in[3]$, ties the other clause candidates and has a path to every other
candidate while no candidate has a path to this clause candidate.888Note that
all paths have a strength of two, as there are no other edge weights in the
weighted majority graph. Each remaining candidate, including the distinguished
candidate $p$, ties every other candidate except for the six clause
candidates, to whom they lose. Thus the six clause candidates $c_{1}^{1}$,
$c_{1}^{2}$, $c_{1}^{3}$, $c_{2}^{1}$, $c_{2}^{2}$, and $c_{2}^{3}$ are the
Schulze winners of the election. Now we want to delete at most two candidates
to make $p$ a winner of the election. Consider the assignment
$x_{1}=\textsc{true}$, which satisfies the first clause, and
$x_{2}=\textsc{true}$, which satisfies the second clause of the CNF formula
$\varphi$, i.e., we have a yes-instance of 3SAT.999The truth assignment of
$x_{3}$ is irrelevant, as both clauses and thus the formula $\varphi$ are
already true due to the truth assignment of $x_{1}$ and $x_{2}$. To ensure
that $p$ is a winner of the election, it is necessary to destroy each path
from a clause candidate to $p$. Menton and Singh Menton and Singh [2013] argue
that in order to do so, it is sufficient to “delete one literal candidate for
each clause, selecting a literal that is satisfied by the satisfying
assignment for $Cl$.” However, if we delete the literal candidates $x_{1}^{1}$
and $x_{2}^{2}$, there is still a path from the candidates
$c_{2}^{1},c_{2}^{2},$ and $c_{2}^{3}$, traversing $x_{2}^{1}$ and $n_{1}^{i}$
with $1\leq i\leq 3$, to the distinguished candidate $p$. Therefore,
$P{(c_{2}^{i},p)}>P{(p,c_{2}^{i})}$ for $i\in[3]$ and thus $p$ is still not a
Schulze winner of the election.

We now argue that $p$ cannot be made a Schulze winner of the election by
deleting any other possible choice of $k=2$ candidates, so we indeed have a
no-instance of Schulze-CCDC. First, there are $k+1=3$ candidates in each group
of clause candidates $C_{i}$ and negation candidates $N_{ijmn}$, and since all
of them have the same incoming and outgoing edges in the WMG, deleting only
two of them cannot make $p$ a Schulze winner of the election. Further,
deleting candidate $a$ would result in $p$ losing to all literal candidates in
$L$. Therefore, the only way to guarantee $p$‘s victory is to delete two of
the literal candidates $x_{1}^{j},x_{2}^{j}$ for $j\in[k+1]$. It is easy to
see that at least one literal candidate for each clause must be deleted to
break the paths between all clause candidates and $p$. It thus suffices to
consider only those pairs of literal candidates where $i=1$ for one and $i=2$
for the other. The following table lists those candidates to whom $p$ loses
when the pair in the corresponding column is deleted, thus preventing $p$ from
becoming a Schulze winner of the election:  deleted pair $x_{1}^{1}$
$x_{1}^{1}$ $x_{1}^{1}$ $x_{1}^{2}$ $x_{1}^{2}$ $x_{1}^{2}$ $x_{1}^{3}$
$x_{1}^{3}$ $x_{1}^{3}$ $x_{2}^{1}$ $x_{2}^{2}$ $x_{2}^{3}$ $x_{2}^{1}$
$x_{2}^{2}$ $x_{2}^{3}$ $x_{2}^{1}$ $x_{2}^{2}$ $x_{2}^{3}$ wins against $p$
$n^{j}_{1}$ $c^{j}_{2}$ $c^{j}_{2}$ $c^{j}_{1}$ $c^{j}_{i}$ $c^{j}_{i}$
$c^{j}_{1}$ $c^{j}_{i}$ $c^{j}_{i},~{}n^{j}_{2}$
Note that $j\in[k+1]$ and $i\in[2]$. This shows that a yes-instance of
$\mathrm{3\textsc{SAT}}$ has been mapped to a no-instance of Schulze-CCDC by
the reduction in the proof of [Menton and Singh, 2013, Thm. 2.2].

Proof of Theorem 2. The proof is analogous to that of Theorem 1, only the
voter lists must be adapted as follows:

$\\#$ | preferences | for each
---|---|---
$3$ | $W{(c_{i}^{j},x_{i}^{1})}$ |  $i\in[k]$, $j\in[k+1]$
$3$ | $W{(x_{i}^{1},x_{i}^{2})}$ | $i\in[k]$
$3$ | $W{(x_{i}^{2},x_{i}^{3})}$ | $i\in[k]$
$3$ | $W{(x_{i}^{3},p)}$ | $i\in[k]$
$4$ | $W{(a,x)}$ | $x\in L$
$4$ | $W{(p,a)}$ |
$1$ | $W{(n,p)}$ | $n\in N$
$2$ | $W{(a,c)}$ | $c\in K$
$2$ | $W{(x_{i}^{j},n^{l}_{ijmn})}$ |  $l\in[k+1]$ where $x_{m}^{n}$ is the negation of $x_{i}^{j}$

∎ Theorem 2

##  Appendix D Variations of Destructive Control in Schulze Elections

Control with the additional twist of candidate groups was introduced by
Erdélyi et al. Erdélyi et al. [2015] as one of their “more natural” models of
electoral control. Intuitively, all candidates are assigned some group (i.e.,
a label) and control actions can only consider whole groups of candidates. For
example, one cannot simply delete a candidate without also deleting all other
candidates of that same group. As noted by Erdélyi et al. Erdélyi et al.
[2015], resistance to the standard control problem carries over to the variant
with groups. However, the reverse is not always true. A voting rule may very
well be vulnerable to the standard control problem, but resistant once groups
are introduced. In the following, we will denote the group variant of a
control problem by appending the suffix G, e.g., DCACG for Destructive Control
by Adding Candidate Groups.

Ranked pairs voting is resistant to standard variants of manipulation,
bribery, and control by deleting as well as adding candidates. All
subsequently considered control problems are either solved in previous
sections (Corollary 3) or resistance carries over from the standard control
problems. Consequently, in this section we focus on the Schulze method only.

Following the approach by Menton and Singh Menton and Singh [2013], we study
the relation of the given problems to variations of minimum vertex cut. First,
we define two variations of Path-Preserving Vertex Cut, called Maximum-
Inclusion Path-Preserving Vertex Cut and Colored Path-Preserving Vertex Cut.

In Maximum-Inclusion Path-Preserving Vertex Cut, we are looking for a set of
vertices such that no path from $s$ to $t$ is present while a path from $t$ to
$s$ remains, with the additional twist that one must include a given number of
labeled vertices.

Maximum-Inclusion Path-Preserving Vertex Cut
---
Given: |  A directed graph $G=(V,E)$, where $V$ contains some labeled vertices $V_{l}\subset V$, two vertices $s,t\in V$ with $s\neq t$, and two integers $x$ and $y$.
Question: |  Is there a subset $V^{\prime}\subseteq V$ such that $V^{\prime}$ is a path-preserving vertex cut and $\lvert V^{\prime}\setminus V_{l}\rvert\leq x$ and $\lvert V^{\prime}\cap V_{l}\rvert\geq y$?

In Colored Path-Preserving Vertex Cut, we are given a graph with colored
vertices and each color must either be fully included in the cut set or not at
all. Note that this also applies to $s$ and $t$, and vertices with their
colors must not be in the cut set. For a vertex $v$, we define
$\mathrm{col}(v)$ to return $v$’s color, and we define
$V[\mathrm{col}]\subseteq V$ to be the set of vertices with the given color
$\mathrm{col}$.

Colored Path-Preserving Vertex Cut
---
Given: |  A directed graph $G=(V,E)$, where each vertex is colored by $\mathrm{col}$, two vertices $s,t\in V$ with $s\neq t$, and an integer $k$.
Question: |  Is there a subset $V^{\prime}\subseteq V$ such that $V^{\prime}$ is a path-preserving vertex cut, $\lvert V^{\prime}\rvert\leq k$, and $V[\mathrm{col}(v)]\subseteq V^{\prime}$ for each $v\in V^{\prime}$?

To show that Schulze is _vulnerability-combining_ (which according to
[Faliszewski et al., 2011, Definition 4.8] means that combining only
vulnerable prongs leads to vulnerability to the resulting multimode attacks)
and thus to fully classify multimode control in Schulze elections, it suffices
to show that Schulze-DCAC+DC is polynomial-time solvable. By reducing Schulze-
DCAC+DC to Maximum-Inclusion Path-Preserving Vertex Cut, we transfer this
challenge to solving whether Maximum-Inclusion Path-Preserving Vertex Cut is
solvable in polynomial time.

######  Proposition 1.

In the nonunique-winner model, Schulze-DCAC+DC polynomial-time Turing-reduces
to Maximum-Inclusion Path-Preserving Vertex Cut.

###### Proof.

Consider a Schulze-DCAC+DC instance $(C,D,V,p,\ell_{AC},\ell_{DC})$. We start
by checking the trivial cases. First, if $p$ is not a Schulze winner of
$(C,V)$, then the destructive goal of the chair is accomplished without having
to add or delete any candidate. Second, if $p$ is a Condorcet winner of the
election $(C\cup D,V)$, then control is impossible.101010Note that Condorcet
voting is immune to destructive control by deleting candidates Hemaspaandra et
al. [2007] (i.e., no matter which candidates are deleted from
$C\setminus\\{p\\}$, a Condorcet winner $p$ cannot be dethroned). Further, no
matter which candidates from $D$ are added to $C$ (even if all candidates from
$D$ are added), $p$ remains a Condorcet winner. Finally, Schulze is Condorcet-
consistent, so a Condorcet winner is also a Schulze winner. If none of these
cases are true, we continue as follows. We first label all candidates from $D$
and then add them to the given election $(C,V)$ to receive a weighted majority
graph, where all candidates from $D$ are labeled, while all original
candidates from $C$ remain unlabeled. Now we iterate through all candidates to
check if we can make $p$ lose against one of them. This can now be done
similarly to the proof of [Menton and Singh, 2013, Lemma 2.4], except for the
following: Instead of applying a subroutine for solving Path-Preserving Vertex
Cut, we apply a subroutine for solving Maximum-Inclusion Path-Preserving
Vertex Cut, where $x=\ell_{DC}$ and $y=|D|-\ell_{AC}$. We return “yes” if we
ever receive a positive result from this call; otherwise, we return “no.” This
is correct, as we return “yes” if and only if we have deleted (at most)
$\ell_{DC}$ unlabeled candidates while (at most) $\ell_{AC}$ candidates from
$D$ remain in the controlled election. ∎

In DCAC+DC, the limit of how many candidates may be added, $\ell_{AC}$, and
the limit of how many candidate may be deleted, $\ell_{DC}$, bear no relation
to one another. For the exact variant of this multimode control problem and
for control by replacing candidates, this is different, though, and we need to
reflect this in the vertex cut. For the reduction to apply to Schulze-EDCAC+DC
and Schulze-DCRC, we thus need to change how the limits in the vertex cut are
handled. That is, we need to (a) set an exact number of unlabeled as well as
an exact number of labeled vertices included in the vertex cut for Schulze-
EDCAC+DC, and (b) set these two numbers to be actually the same for Schulze-
DCRC.

######  Proposition 2.

In the nonunique-winner model, Schulze-DCDCG and Schulze-DCACG polynomial-time
Turing-reduces to Colored Path-Preserving Vertex Cut.

###### Proof.

Our proof for the reduction of Destructive Control by Deleting Candidate
Groups and Destructive Control by Adding Candidate Groups works similar to the
proof of [Menton and Singh, 2013, Lemma 2.4], but instead of applying a
subroutine for solving Path-Preserving Vertex Cut, we apply one for solving
Colored Path-Preserving Vertex Cut. ∎

While we do not know the complexity of Maximum-Inclusion Path-Preserving
Vertex Cut and Colored Path-Preserving Vertex Cut yet, by Propositions 1 and 2
membership of these variants of vertex cut in $\mathrm{P}$ immediately gives
$\mathrm{P}$ results for the control problems DCDCG and DCACG in Schulze
elections. Note that the standard vertex cut problem can be solved in
polynomial time West [2017].

$x_{a3}$$x_{a1}$$x_{a2}$$y$$x_{b3}$$x_{b1}$$x_{b2}$$z_{a1}$$z_{a2}$$z_{b1}$$z_{b2}$$d$$c$$5$$5$$5$$5$$10$$10$$10$$10$$20$$20$$20$$20$$20$$20$$20$$20$$20$$20$$20$$20$$10$$10$$10$$10$$10$$10$$10$$10$$5$$5$$5$$1$$1$$1$$1$
Figure 8: A WMG of an election where for $\ell=2$ control by deleting
candidates is possible in the unique-winner model but impossible in the
nonunique-winner model. The edge width visually illustrates the edge weight.

##  Appendix E Schulze Is Vulnerable to Destructive Control by Deleting
Candidates

In this section, we give a polynomial-time algorithm for solving Schulze-DCDC
in the nonunique-winner model.

Consider an election $(C,V)$ and a corresponding control instance
$((C,V),d,\ell)$ of Schulze-DCDC. If the despised candidate $d$ initially is a
Schulze winner of $(C,V)$, our goal is to find a candidate $c$ with a stronger
path to $d$ than $d$ has to $c$ by deleting at most $\ell$ candidates. The
algorithm works as follows.

First, if the despised candidate $d$ is already not a Schulze winner of
$(C,V)$, return true. Otherwise, iterate over the set of candidates
$C\setminus\\{d\\}$. For each candidate $c\in C\setminus\\{d\\}$, we check
whether $c$ is a possible rival of $d$. If $d$ beats $c$ directly, i.e., the
edge from $d$ to $c$ is stronger than any path from $c$ to $d$, we exclude $c$
as a rival and move on to the next possible candidate. Additionally, if
$P[c,d]=0$, we also exclude $c$ and move on. Otherwise, $c$ is a possible
rival of $d$ and we move on to the deletion stage and initialize a deletion
counter $ctr=0$ for this candidate $c$. Next, for the graph $G$ of all
stronger paths from $d$ to $c$, i.e., all paths where the strength of the path
is greater than $P[c,d]$, we check whether deleting the in-neighbors
$N^{+}_{G}(c)$ of $c$ is possible within our deletion limit and accomplishes
our goal of dethrowning $d$: We increment the deletion counter by $ctr+=\lvert
N^{+}_{G}(c)\rvert$ and check whether $ctr>\ell$; if so, we move on to the
next possible candidate; otherwise, we delete $N^{+}_{G}(c)$ from the original
election. If $d$ is not a Schulze winner of the election after deletion,
return true. If $d$ still wins, we have cut a path from $c$ to $d$ by deleting
$N^{+}_{G}(c)$. Repeat the above steps until either the deletion limit is
reached or $d$ is not a winner of the election anymore. Finally, if there is
no candidate such that deleting at most $\ell$ candidates makes this candidate
win against $d$, return false.

Proof of Theorem 4. We first show that the algorithm runs in polynomial time,
and prove correctness thereafter. The algorithm contains several subroutines
all of which can be executed in polynomial time. First, the winner problem for
Schulze is known to be solvable in polynomial time Schulze [2011].111111The
Schulze voting method was recently examined through the lens of fine-grained
complexity by Sornat et al. Sornat et al. [2021]. Then we use a subroutine to
construct a graph of the stronger paths from the despised candidate to some
other candidate $c\in C$, a possible rival of $d$. This construction can be
done in polynomial time by adapting the algorithm for solving the winner
problem for Schulze, which itself is an adaption of the Floyd–Warshall
algorithm for determining shortest paths in a directed weighted graph.
Finally, the loop over all candidates is bounded by the number of candidates,
and the execution of the subroutines in the loop is bounded by the deletion
limit $\ell$. Overall, the algorithm runs in polynomial time.

We now show that the algorithm will always return true if $((C,V),d,\ell)$ is
a yes-instance of Schulze-DCDC, and will return false otherwise.

Assume that $((C,V),d,\ell)$ is a yes-instance of Schulze-DCDC, that is, there
exists a subset of candidates $C^{\prime}\subset C$ such that $\lvert
C^{\prime}\rvert\leq\ell$ and $d$ is not a Schulze winner of the election
$(C\setminus C^{\prime},V)$. By Theorem 3, we know that it suffices to
consider the in-neighborhood of candidates $c\in C\setminus\\{d\\}$ to
determine whether one of them beats $d$ by deleting at most $\ell$ candidates.
Obviously, our algorithm always finds such a candidate (whenever there exists
one) and thus returns true.

Assume that $((C,V),d,k)$ is a no-instance of Schulze-DCDC, that is, there
exists no subset of candidates $C^{\prime}\subset C$ with $\lvert
C^{\prime}\rvert\leq\ell$ such that $d$ is not a Schulze winner of the
election $(C\setminus C^{\prime},V)$. Since any set of candidates $C^{\prime}$
for which control is successful must be greater than $\ell$ and by Theorem 3
the smallest such set can be found in the neighborhood of some $c\in
C\setminus\\{d\\}$, we have that the algorithm will always exceed the deletion
counter and thus return false after examining every $c\in C\setminus\\{d\\}$.
∎ Theorem 4

Unfortunately, we cannot easily transfer our algorithm to work in the unique-
winner model. In this model, the goal is to prevent the sole victory of a
despised candidate $d$. In addition to outright beating $d$, this goal can
also be achieved by making a candidate win alongside $d$. This leads to a
situation where some candidate $c$ ties the despised but the victory of $c$ is
dependent on all other candidates in the election. It is possible that the
same election, along with $d$ and the deletion limit $\ell$, gives a yes-
instance in the unique-winner model and a no-instance in the nonunique-winner
model. In Figure 8, we give an example for this scenario. Candidate $d$ is the
unique winner of the election. It is impossible to prevent $d$ from winning
altogether by deleting at most two candidates. However, by deleting both
$x_{a1}$ and $x_{b1}$ we can prevent $d$ from being the sole winner of the
election, as candidate $c$ will win alongside $d$. Note that this can only be
achieved by deleting $x_{a1}$ and $x_{b1}$ neither of which are in-neighbors
of $c$.

##  Appendix F Deferred Proofs from Section 5

Proof of Lemma 3. Let $(C,V)$ be an election and $x$ a new candidate. Let
$(C\cup\\{x\\},V^{x})$ be the election where candidate $x$ is added to every
vote in $V$ as the least preferred option. Clearly, we have
$N_{V^{x}}{(x,c)}=0$ and thus $D_{V^{x}}{(x,c)}=-\lvert V^{x}\rvert$ for all
$c\in C\setminus\\{x\\}$.

For Schulze, it follows that in the WMG candidate $x$ has an incoming edge
with weight $\lvert V^{x}\rvert$ for every $c\in C$ and the outdegree of $x$
is $0$. Thus candidate $x$ cannot win and can also not be part of any path
between any other candidates $c,c^{\prime}\in C$. Ultimately, $x$ has no
influence whatsoever on the election.

For ranked pairs, it follows that the pair $(c,x)$ will be in the top ranking
for each $c\in C$ (possibly among others). These pairs will be added in the
first round of rankings, leaving a graph where the vertex $x$ will have no
outgoing edges and any edge to $x$ cannot be part of a cycle. Therefore, all
other rankings and edges in the graph are untouched. The winner of election
$(C\cup\\{x\\},V^{x})$ is the same as of election $(C,V)$. ∎ Lemma 3

Proof of Corollary 1. Schulze and ranked pairs are IBC (see Lemma 3), from
Theorem 1 we know that Schulze-CCDC is $\mathrm{NP}$-hard, and Parkes and Xia
Parkes and Xia [2012] showed $\mathrm{NP}$-hardness of Ranked-Pairs-CCDC.
Hence, by the result of Lorregia et al. Loreggia et al. [2015], Schulze-CCRC
and Ranked-Pairs-CCRC are also $\mathrm{NP}$-hard. It is easy to see that
Schulze-CCRC and Ranked-Pairs-CCRC are in $\mathrm{NP}$ and thus,
$\mathrm{NP}$-complete.121212As noted earlier, we use a fixed tie-breaking
scheme to ensure tractability. ∎ Corollary 1

Proof of Corollary 2. By Lemma 1, we can extend the proof of Corollary 1 to
Schulze-ECCAC+DC, Schulze-ECCRC, Ranked-Pairs-ECCAC+DC, and Ranked-Pairs-
ECCRC. ∎ Corollary 2

Proof of Corollary 3. By Lemma 3, ranked pairs is IBC and Parkes and Xia
Parkes and Xia [2012] showed $\mathrm{NP}$-hardness for Ranked-Pairs-DCDC. By
the result of Lorregia et al. Loreggia et al. [2015], Ranked-Pairs-DCRC is
also $\mathrm{NP}$-hard. Since Ranked-Pairs-DCRC is in $\mathrm{NP}$, it is
$\mathrm{NP}$-complete. By Lemma 2, this also applies to Ranked-Pairs-EDCAC+DC
and Ranked-Pairs-ECCRC. ∎ Corollary 3

Proof of Theorem 5. It is easy to see that Schulze-ECCAV+DV, Schulze-CCRV,
Schulze-EDCAV+DV and Schulze-DCRV are in $\mathrm{NP}$. To show
$\mathrm{NP}$-hardness, we reduce from the $\mathrm{NP}$-complete problem
Restricted Exact Cover By 3-Sets (RX3C) Gonzalez [1985]: Given a set
$B=\\{b_{1},\ldots,b_{3s}\\}$ with $s\geq 1$ and a list
$\mathcal{S}=\\{S_{1},\ldots,S_{3s}\\}$, where
$S_{i}=\\{b_{i,1},b_{i,2},b_{i,3}\\}$ and $S_{i}\subseteq B$ for all
$S_{i}\in\mathcal{S}$ and each $b_{j}$ is contained in exactly three sets
$S_{i}\in\mathcal{S}$, does there exist an exact cover, i.e., a sublist
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such that each $b_{i}\in B$ occurs
in exactly one $S_{i}\in\mathcal{S}^{\prime}$?

Let $(B,\mathcal{S})$ be an RX3C instance, such that $3s=n$. We first present
the reduction in the nonunique-winner model; the slightly adapted reduction
for the unique-winner model will be considered later. Let
$\ell_{AV}=\ell_{DV}=s$ for the Schulze-ECCAV+DV and Schulze-EDCAV+DV
instances we construct, and let $\ell_{RV}=s$ for the Schulze-CCRV and
Schulze-DCRV instances. Further, let $\mathcal{L}\gg s$ be a constant much
greater than $s$.131313The precise value of $\mathcal{L}$ is not important;
all that matters is that when used as an edge weight in a WMG, $\mathcal{L}$
is large enough, such that any edge changed by the control actions must not
change in direction, i.e., the sign of the edge weight must not flip. Recall
that the strength of a path in a WMG is specified as the weight of the weakest
edge on the path. From $(B,\mathcal{S})$ we construct an election $(C,V)$ as
follows. Let the candidate set be

$C=B\cup\\{p,w\\}.$

The list of votes contains $\ell_{DV}$ votes of the form $w\,B\,p$ and the
remaining votes are constructed such that

  * •

$p$ beats $w$ by $2\mathcal{L}$ votes,

  * •

each $b_{i}$ beats $p$ by $2\mathcal{L}+2\ell_{DV}+2\ell_{AV}-2$ votes,

  * •

$w$ beats each $b_{i}$ by votes $\gg 2\mathcal{L}$ (so as to make these edges
not relevant for the strength of a path), and

  * •

all other pairwise differences are $0$ or at least smaller than $\mathcal{L}$.

The WMG of the resulting election is shown in Figure 9. Note that candidate
$w$ is the unique winner of the election.

$b_{2}$$b_{1}$$\ldots$$b_{3s}$$p$$w$$\gg 2\mathcal{L}$$\gg 2\mathcal{L}$$\gg
2\mathcal{L}$$2\mathcal{L}$pt$2\mathcal{L}+2\ell_{DV}$$+2\ell_{AV}-2$pt$2\mathcal{L}+2\ell_{DV}$$+2\ell_{AV}-2$$2\mathcal{L}+2\ell_{DV}+2\ell_{AV}-2$
Figure 9: The WMG of the election $(C,V)$ from the proof of Theorem 5.

The list of additional votes $U$ contains one vote

$S_{i}\,p\,(B\setminus S_{i})\,w\hskip 14.22636pt\text{for each}\
S_{i}\in\mathcal{S}.$

Let $p$ be the distinguished candidate for the constructive case and $w$ be
the despised candidate for the destructive case. We claim that $p$ can be made
a Schulze winner (and $w$ can be prevented from being the unique Schulze
winner) by adding exactly $\ell_{AV}$ voters and deleting exactly $\ell_{DV}$
voters if and only if $(B,\mathcal{S})$ is a yes-instance of RX3C.

From left to right, let $(B,\mathcal{S})$ be a yes-instance of RX3C and let
$\mathcal{S}^{\prime}\subset\mathcal{S}$ be an exact cover of $B$. We have
$\lvert\mathcal{S}^{\prime}\rvert=s$. Remove $\ell_{DV}$ votes from $V$ of the
form $w\,B\,p$ and add $s$ votes $S_{i}\,p\,(\mathcal{S}\setminus S_{i})\,w$
from $U$, where $S_{i}\in\mathcal{S}^{\prime}$. Let $V^{\prime}$ be the
resulting list of votes. Due to the construction, each strongest path from any
candidate to another one can only be composed of edges where the edge weight
is greater than $2\mathcal{L}$, and each edge with a weight that is much
greater than $2\mathcal{L}$ has no influence on the strength of the strongest
path. Therefore, it suffices to calculate the weight changes of edges to and
from $p$. In the added votes from $U$ we have $b_{j}\succ p$ in exactly one
vote and $p\succ b_{j}$ in the remaining $s-1$ votes for each $b_{j}\in B$.
Therefore, $p$ gains $(s-1)-1$ in each pairwise comparison to $b_{j}\in B$. By
adding the $s$ votes from $U$,

  * •

$p$ gains $s-2=\ell_{AV}-2$ against each $b_{j}\in B$, and

  * •

$p$ gains $s=\ell_{AV}$ against $w$.

By deleting the $\ell_{DV}$ votes from $V$,

  * •

$p$ gains $\ell_{DV}$ against each $b_{j}\in B$, and

  * •

$p$ gains $\ell_{DV}$ against $w$.

We have $D_{V^{\prime}}{(p,b_{j})}=2\mathcal{L}+\ell_{DV}+\ell_{AV}$ for each
$b_{j}\in B$ and $D_{V^{\prime}}{(p,w)}=2\mathcal{L}+\ell_{DV}+\ell_{AV}$.
Thus we have
$\text{str}_{V^{\prime}}{(p,c)}=2\mathcal{L}+\ell_{DV}+\ell_{AV}=\text{str}_{V^{\prime}}{(c,p)}$
for each $c\in C\setminus\\{p\\}$, so $p$ is a Schulze winner of the election
$(C,V^{\prime})$, which resulted from $(C,V)$ by adding $s=\ell_{AV}$ voters
and deleting $s=\ell_{DV}$ voters. Both the constructive and destructive
control actions were successful in the nonunique-winner model.

$b_{2}$$b_{1}$$\ldots$$b_{3s}$$p$$w$$\gg 2\mathcal{L}$$\gg 2\mathcal{L}$$\gg
2\mathcal{L}$$2\mathcal{L}+\ell_{DV}+\ell_{AV}$$2\mathcal{L}+\ell_{DV}+\ell_{AV}$pt$2\mathcal{L}+\ell_{DV}$$+\ell_{AV}$$2\mathcal{L}+\ell_{DV}+\ell_{AV}$
Figure 10: The WMG of the resulting election $(C,V^{\prime})$ from the proof
of Theorem 5 after successful control.

From right to left, let $(B,\mathcal{S})$ be a no-instance of RX3C. Hence, we
know that in any $\mathcal{S}^{\prime}\subset\mathcal{S}$ with
$\lvert\mathcal{S}^{\prime}\rvert=s$ at least one $b_{j}$ is contained in more
than one $S_{i}\in\mathcal{S}^{\prime}$. The difference between the strength
of a strongest path from $w$ to $p$ and the strength of a strongest path from
$p$ to $w$ is
$\text{str}_{V}{(b_{j},p)}-\text{str}_{V}{(p,b_{j})}=2\ell_{DV}+2\ell_{AV}-2$.
By deleting $\ell_{DV}$ voters, $p$ can make up at most $2\ell_{DV}$ and a
difference of $2\ell_{AV}-2$ remains. In any subset $U^{\prime}$ of
$s=\ell_{AV}$ votes from $U$ we have one $b_{j}\in B$ with
$N_{U^{\prime}}{(b_{j},p)}>1$ and, therefore,
$D_{U^{\prime}}{(p,b_{j})}\leq\ell_{AV}-4$. It follows that at least one
$b_{j}\in B$ with $\text{str}_{V}{(b_{j},p)}\geq
2\mathcal{L}+\ell_{DV}+\ell_{AV}$ exists and, therefore, it holds that
$P{(w,p)}>P{(p,w)}$, so $p$ cannot be made a Schulze winner by adding
$s=\ell_{AV}$ votes and deleting $s=\ell_{DV}$ votes. Since $p$ is the only
candidate where the difference in the strength of a strongest path against $w$
is less than $2\ell_{DV}+\ell_{AV}$, it follows that a sole victory of
candidate $w$ cannot be prevented.

For the unique-winner model, we need to slightly adapt the above construction.
In the voter list $V$, we need to have every $b_{j}$ win against $p$ by
$2\mathcal{L}+2\ell_{DV}+2\ell_{AV}-3$ votes. We then claim that $p$ can be
made a _unique_ Schulze winner (and $w$ can be prevented from being a winner)
by adding exactly $\ell_{AV}$ voters and deleting exactly $\ell_{DV}$ voters
if and only if $(B,\mathcal{S})$ is a yes-instance of RX3C. The proof of
correctness for this slightly modified reduction is analogous. Moreover,
$\mathrm{NP}$-hardness of Schulze-CCRV and Schulze-DCRV can also be shown
analogously in both winner models. ∎ Theorem 5

Proof of Theorem 6. We slightly adapt the construction used in the proof of
Theorem 5 and therefore only provide the overall reduction. Instead of having
the pairwise differences between each pair of candidates $b_{i},b_{j}\in B$ be
zero, we have each $b_{i}$ win by $\gg 2\mathcal{L}$ against all $b_{j}\in B$,
where $i<j$, i.e.,

$D(b_{i},b_{j})\gg 2\mathcal{L}\hskip 28.45274pt\forall i<j,\ 1\leq i,j\leq
3s.$

This ensures that no cycles can be formed by inserted edges between any pair
of candidates from $B$. The rest of the construction remains the same. By
writing $(c,c^{\prime})$ we denote the pair of candidates $c$ and $c^{\prime}$
and—slightly overloading the notation—we use $(c,M)$ to denote all pairs
$(c,m)$ where $m\in M$.

In the resulting election, the first ranking of pairwise differences contains
all pairs $(w,B)$ and $(b_{i},b_{j})$, $i<j$, $1\leq i,j\leq 3s$. As no cycle
can be created by adding these pairs, all edges are added. The next ranking
are all pairs $(B,p)$. Again, no cycle can be created and all edges are added.
However, the remaining pair $(p,w)$ would create an edge from $p$ to $w$,
which would induce a cycle. Candidate $w$ remains the sole source and is the
unique ranked pairs winner of the election.

We claim that $p$ can be made a ranked pairs winner (and $w$ can be prevented
from being the unique ranked pairs winner) by adding exactly $\ell_{AV}$
voters and deleting exactly $\ell_{DV}$ voters if and only if
$(B,\mathcal{S})$ is a yes-instance of RX3C.

From left to right, let $(B,\mathcal{S})$ be a yes-instance of RX3C and let
$\mathcal{S}^{\prime}\subset\mathcal{S}$ be an exact cover of $B$. Remove
$s=\ell_{DV}$ votes from $V$ of the form $w\,B\,p$ and add $s=\ell_{AV}$ votes
$S_{i}\,p\,(B\setminus S_{i})\,w$ from $U$, where
$S_{i}\in\mathcal{S}^{\prime}$. The resulting pairwise differences for all
pairs are as follows:

$\displaystyle D(w,B)\gg 2\mathcal{L},$ $\displaystyle
D(B,p)=2\mathcal{L}+\ell_{DV}+\ell_{AV},\text{ and}$ $\displaystyle
D(p,w)=2\mathcal{L}+\ell_{DV}+\ell_{AV}.$

Assuming a fixed tie-breaking scheme, where the preferred candidate is always
favored, we add the pair $(p,w)$ before any of the pairs $(B,p)$, which will
then create an edge and thus be skipped. Candidate $p$ is the only source and
unique ranked pairs winner of the election.

From right to left, let $(B,\mathcal{S})$ be a no-instance of RX3C. Hence, it
holds that in any $\mathcal{S}^{\prime}\subset\mathcal{S}$ with
$\lvert\mathcal{S}^{\prime}\rvert=s$ at least one $b_{i}$ is contained in more
than one $S_{i}\in\mathcal{S}^{\prime}$. If $D(b_{i},p)>D(p,w)$ holds for even
one $b_{i}\in B$, the pair $(b_{i},B)$ will be ranked above $(p,w)$ and
therefore added. When considering $(p,w)$, a path from $w$ to $p$ already
exists and therefore the edge is skipped. The only way to prevent $w$ from
being a unique winner and making $p$ the unique winner is to ensure
$D(B,p)\leq D(p,w)$. By the same argumentation as in the proof of Theorem 5,
we cannot make up the pairwise difference unless each $b_{i}\in B$ is present
in exactly one $S_{i}\in\mathcal{S}^{\prime}$, which is a contradiction to
$(B,\mathcal{S})$ being a no-instance of RX3C. ∎ Theorem 6