# Parameterized Complexity of Multiwinner Determination:
More Effort Towards Fixed-Parameter Tractability††thanks: A $3$-page extended
abstract of the paper appeared in the proceedings of the _17th International
Conference on Autonomous Agents and Multiagent Systems_ (AAMAS 2018) [81].

Yongjie Yanga and Jianxin Wangb,c

( aChair of Economic Theory, Saarland University, Saarbücken 66123, Germany
<EMAIL_ADDRESS>
bSchool of Computer Science and Engineering, Central South University,
Changsha 410083, China
cXiangjiang Laboratory, Changsha 410205,China
<EMAIL_ADDRESS>)

###### Abstract

We study the parameterized complexity of winner determination problems for
three prevalent $k$-committee selection rules, namely the minimax approval
voting (MAV), the proportional approval voting (PAV), and the Chamberlin-
Courant’s approval voting (CCAV). It is known that these problems are
computationally hard. Although they have been studied from the parameterized
complexity point of view with respect to several natural parameters, many of
them turned out to be W[1]-hard or W[2]-hard. Aiming at obtaining plentiful
fixed-parameter algorithms, we revisit these problems by considering more
natural single parameters, combined parameters, and structural parameters.

Keywords: multiwinner voting, fixed-parameter tractability, minimax approval
voting, proportional approval voting, Chamberlin-Courant’s approval voting,
treewidth, W[1]-hard

##  1 Introduction

Committee selection rules (a.k.a. multiwinner voting rules) have received a
considerable amount of attention recently due to their broad applications in
social choice, multi-agent systems, recommendation systems, etc. [32, 40, 41,
50]. How efficiently winning candidates with respect to a committee selection
rule can be calculated is one of the most significant criteria to evaluate the
applicability of these rules. Many rules, such as STV, Bloc, $k$-Borda,
approval voting, satisfaction approval voting, admit polynomial-time
algorithms for computing winners [4, 29]. However, there are also salient
committee selection rules with respect to which winners are NP-hard to
compute. Among them are particularly the minimax approval voting (MAV) [12,
51], the proportional approval voting (PAV) [4, 44, 71], and the Chamberlin-
Courant’s approval voting (CCAV) [19, 62]. Nevertheless, as these rules
possess their own merits in many other aspects [3, 34, 44, 45, 50],
researchers investigated the parameterized complexity of winner determination
problems under these rules, with the hope of procuring as many fixed-parameter
tractability results as possible. While many realistic parameters have been
considered in the literature so far, there are still many relevant but
underappreciated parameters. This paper aims to take a further step towards
breaking the complexity barrier against the applicability of the above-
mentioned three approval-based rules by extensively expanding the set of
meaningful parameters leading to FPT-algorithms for the winner determination
problems. Notably, in addition to many traditional parameters, we also study
several structural parameters of the incidence graphs of approval-based
elections. The incidence graph of an approval-based election is a bipartite
graph whose vertex set is the candidate set union the voter set, and there is
an edge between a candidate and a voter if and only if this voter approves the
candidate. To date, less is known about whether some structural parameters of
the incidence graphs such as the treewidth and the size of a maximum matching
lead to some FPT-algorithms. These parameters are intimately connected to
several important single parameters. For example, they are lower bounds of
both the number of candidates $m$ and the number of voters $n$, and hence any
FPT-algorithm with respect to these two structural parameters directly carry
over to $m$ and $n$.

Organization. In Section 2, we give definitions and notations used in the
paper. Then, we elaborate on related works and summarize our main results in
Section 3. Our concrete results are encapsulated in Sections 4–6.
Specifically, Section 4 studies single parameters, Section 5 explores
combinations of the single parameters occurring in Section 4, and Section 6
focuses on the aforementioned structural parameters. For an overview of our
main results, we refer to Table 1. We complete the paper by recapping our
contributions and laying out several promising avenues for future research in
Section 7.

##  2 Preliminaries

In this section, we give essential notions related to our study.

###  2.1 Elections

We study approval-based multiwinner voting. In this setting, an election is a
tuple $E=(C,V)$ where $C$ is a set of candidates and $V$ is a multiset of
votes. Each vote of $V$ is cast by a voter and is defined as a subset of $C$.
In this paper, we interchangeably use the terms vote and voter. We say that a
vote $v$ approves a candidate $c$ if $c\in v$. For each candidate $c$, $V(c)$
denotes the set of votes in $V$ approving $c$. Let $k$ be a nonnegative
integer. A $k$-set is a set of cardinality $k$. A committee (respectively,
$k$-committee) is a subset (respectively, $k$-subset) of candidates. A
$k$-committee selection rule maps each election $(C,V)$ and every nonnegative
integer $k$ such that $k\leq|C|$ to a collection of $k$-committees of $C$,
winning $k$-committees of $(C,V)$ under this rule.

The Hamming distance between two sets $v$ and $v^{\prime}$ is defined as

$\mathcal{H}(v,v^{\prime})=|v\setminus v^{\prime}|+|v^{\prime}\setminus v|.$

We study the following $k$-committee selection rules.

MAV

In general, MAV selects $k$-committees as close as possible to every vote,
where the closeness is measured by the Hamming distance. Precisely, the MAV
score of a committee $w$ with respect to $(C,V)$ is
$\textsf{MAV}(V,w)=\max_{v\in V}\mathcal{H}(v,w)$. MAV selects $k$-committees
with the minimum MAV score.

CCAV

A vote $v$ is satisfied with a committee $w$ if and only if at least one of
$v$’s approved candidates is contained in $w$, i.e., $v\cap w\neq\emptyset$.
Candidates in $v\cap w$ are regarded as representatives of $v$ in $w$. The
CCAV score of a committee $w$ with respect to $(C,V)$ is
$\textsf{CCAV}(V,w)=|\\{v\in V:v\cap w\neq\emptyset\\}|$. CCAV selects
$k$-committees with the maximum CCAV score.111CCAV is a special rule of the
class of Chamberlin-Courant’s rules. See [29] for further discussions.

PAV

The PAV score of a committee $w$ with respect to an election $(C,V)$ is
$\textsf{PAV}(V,w)=\sum_{v\in V,v\cap w\neq\emptyset}\sum_{i=1}^{|v\cap
w|}\frac{1}{i}$. PAV selects $k$-committees with the maximum PAV score.

Note that by the above definitions,
$\textsf{CCAV}(V,\emptyset)=\textsf{PAV}(V,\emptyset)=0$ holds.

For each $\tau\in\\{\text{MAV, CCAV, PAV}\\}$, we study the following problem.

$\tau$-Multiwinner
---
Input: |  An election $E=(C,V)$, an integer $k\leq|C|$, and a rational number $d$.
Question: |  Is there a $k$-committee $w\subseteq C$ such that $\tau(V,w)\leq d$ for $\tau=\text{MAV}$, and $\tau(V,w)\geq d$ for $\tau\in\\{\text{CCAV, PAV}\\}$?

Throughout this paper, we study the following single parameters and
consistently use the corresponding notations given below.

  * •

$m=|C|$.

  * •

$n=|V|$.

  * •

$d$: the threshold score of a desired committee.

  * •

$k$: size of winning committees.

  * •

$\overline{k}=m-k$.

  * •

$\triangle_{\text{V}}=\max_{v\in V}|v|$ is the maximum number of candidates a
vote approves.

  * •

$\triangle_{\text{C}}=\max_{c\in C}|V(c)|$ is the maximum number of votes
approving a candidate in common.

The first four parameters are natural and have been substantially covered in
the literature. (See Section 3 for the details.) The study of $\overline{k}$
is motivated by the observation that in many real-life decision-making
scenarios winners are picked by eliminating a small number of losers, or more
relevantly, many decision-making processes are directly designed to select
losers other than selecting winners. The last two parameters
$\triangle_{\text{V}}$ and $\triangle_{\text{C}}$ have been either explicitly
or implicitly studied in the literature. In many real-world applications
voters are allowed to approve only a few candidates. In some other scenarios,
voters are cognitively limited or time constrained so that they are only able
to evaluate a small number of candidates. In these cases,
$\triangle_{\text{V}}$ is relatively small. Regarding the parameter
$\triangle_{\text{C}}$, observe that it is no greater than $n$. So, it is
small whenever $n$ is small. Moreover, as our goal is to provide a landscape
of the parameterized complexity of $\tau$-Multiwinner as complete as possible,
it is theoretically significant to study this parameter so as that we can
offer results for combined parameters including $\triangle_{\text{C}}$.

###  2.2 Graphs

We assume the reader is familiar with the basic concepts of graph theory, and
refer to [13, 74] for notions in graph theory used but not defined in the
paper. We only reiterate some basic notions below. A graph is a pair $(N,A)$
where $N$ is a set of vertices and $A$ is a set of edges over $N$. Each edge
is defined as an unordered pair of vertices, and between every two vertices
there can be at most one edge. A multigraph is a generalization of a graph
where between every two vertices there may exist multiple edges, and there may
exist loops on vertices. A hypergraph is a generalization of a graph where
every edge is a subset of vertices. A multihypergraph is a generalization of a
hypergraph so that there may exist multiple edges consisting of the same
vertices.

A matching of a graph $G=(N,A)$ is a subset $M$ of $A$ such that no two edges
in $M$ share a common vertex. A vertex $v$ is saturated by $M$ if $v$ is a
vertex in some edge in $M$. A maximum matching of $G$ is a matching with the
maximum cardinality among all matching of $G$. We use $\alpha(G)$ to denote
the size of a maximum matching of $G$.

###  2.3 Parameterized Complexity

A parameterized problem is a subset of $\Upsigma^{*}\times\mathbb{N}$, where
$\Upsigma$ is a finite alphabet. A parameterized problem can be either fixed-
parameter tractable (FPT) or fixed-parameter intractable. In particular, a
parameterized problem is FPT if there is an algorithm which correctly
determines for each instance $(I,\kappa)$ of the problem whether $(I,\kappa)$
is a Yes-instance in time $O(f(\kappa)\cdot|I|^{O(1)})$, where $f$ is a
computable function and $|I|$ is the size of $I$. Fixed-parameter intractable
problems are further classified into many classes including W[1]-hard,
W[2]-hard, etc. For greater details on parameterized complexity theory, we
refer to [23, 26, 28].

##  3 Related Works and Our Contributions

In this section, we discuss some important related works and outline our main
contributions.

###  3.1 Single Parameters

$\tau$-Multiwinner has many natural parameters inherent in its definition,
say, the seven single parameters listed at the end of Section 2.1. All these
seven parameters except $\overline{k}$ have been explicitly or implicitly
investigated in the literature prior to our work.

First, it is easy to see that MAV-Multiwinner, CCAV-Multiwinner, and PAV-
Multiwinner are FPT with respect to the parameter $m$. Misra, Nabeel, and
Singh [58] proved that MAV-Multiwinner is FPT with respect to the parameters
$d$ and $n$, but becomes W[2]-hard when parameterized by $k$. Betzler, Slinko,
and Uhlmann [5] proved that CCAV-Multiwinner is FPT with respect to the
parameter $n$, but turned out to be W[2]-hard when $k$ is the parameter.
Moreover, they considered a dual parameter $R=n-d$. They proved that CCAV-
Multiwinner is NP-hard even when $R=0$, but presented an FPT-algorithm with
respect to the combined parameter $k+R$.222A parameterized problem is FPT with
respect to the combination of two parameters $\kappa$ and $\kappa^{\prime}$ if
it is solvable in time $O^{*}(f(\kappa,\kappa^{\prime}))$ where $f$ is a
computable function in $\kappa$ and $\kappa^{\prime}$, or equivalently it is
FPT with respect to $\kappa+\kappa^{\prime}$. Aziz et al. [4] proved that PAV-
Multiwinner is W[1]-hard with respect to $k$ even if every voter approves two
candidates.

We complement these results as follows. First, we close some gaps and improve
an FPT-algorithm. Concretely, we propose an FPT-algorithm for PAV-Multiwinner
when parameterized by $n$. We also observe that CCAV-Multiwinner is equivalent
to the Partial Hitting Set problem, and as a consequence of a previous result
for the Partial Hitting Set problem, CCAV-Multiwinner can be solved in
$O^{*}(2^{O(d)})$ time or in $O^{*}(2^{O(n)})$ time.333$O^{*}()$ is $O()$ with
polynomial factors being omitted. It should be noted that our new observation-
based algorithm substantially improves the previous best FPT-algorithm for
CCAV-Multiwinner parameterized by $n$ studied in [5] which runs in time
$O^{*}(n^{n})$. Second, we study the parameter $\overline{k}=m-k$, the number
of nonwinning candidates. We show that MAV-Multiwinner, CCAV-Multiwinner, and
PAV-Multiwinner are all W[1]-hard with respect to this parameter, even when
every voter approves two candidates. Third, from previous results by other
researchers, we achieve numerous dichotomy results with respect to the two
natural parameters $\triangle_{\text{V}}$ and $\triangle_{\text{C}}$. It is
known that MAV-Multiwinner, CCAV-Multiwinner, and PAV-Multiwinner are already
NP-hard when $\triangle_{\text{V}}=2$ and $\triangle_{\text{C}}=3$ [4, 51,
63]. We prove that MAV-Multiwinner and CCAV-Multiwinner become polynomial-time
solvable if $\triangle_{\text{V}}\leq 1$ or $\triangle_{\text{C}}\leq 2$, and
PAV-Multiwinner becomes polynomial-time solvable if
$\min\\{\triangle_{\text{V}},\triangle_{\text{C}}\\}=1$ or
$\triangle_{\text{V}}=\triangle_{\text{C}}=2$.

###  3.2 Combined Parameters

Obviously, if a problem is FPT with respect to a parameter $\kappa$, it is FPT
with respect to any combined parameter including $\kappa$. As except PAV-
Multiwinner with respect to $d$ whose fixed-parameter tractability is open,
MAV-Multiwinner, CCAV-Multiwinner, and PAV-Multiwinner are FPT with respect to
$m$, $n$, and $d$, it only makes sense to study combinations of other
parameters. As $k+\overline{k}=m$, $\tau$-Multiwinner for
$\tau\in\\{\text{MAV},\text{CCAV},\text{PAV}\\}$ is FPT with respect to
$k+\overline{k}$. For MAV and CCAV, the remaining combinations of two single
parameters are $k+\triangle_{\text{V}}$, $k+\triangle_{\text{C}}$,
$\overline{k}+\triangle_{\text{V}}$, and $\overline{k}+\triangle_{\text{C}}$.
We establish many FPT-results with respect to these combined parameters.
Concretely, we obtain FPT-results for MAV-Multiwinner and CCAV-Multiwinner
when parameterized by $k+\triangle_{\text{C}}$ and
$\overline{k}+\triangle_{\text{C}}$. However, as MAV-Multiwinner, CCAV-
Multiwinner, and PAV-Multiwinner are W[1]-hard with respect to $\overline{k}$
(even when every vote approves two candidates), they are W[1]-hard when
parameterized by $\overline{k}+\triangle_{\text{V}}$. For the parameter
$k+\triangle_{\text{V}}$, we develop an FPT-algorithm for MAV-Multiwinner, but
we show that CCAV-Multiwinner is W[1]-hard even when every vote approves two
candidates. Concerning PAV, a reduction by Aziz et al. [4] implies that PAV-
Multiwinner is W[1]-hard with respect to $k+\triangle_{\text{V}}$. We are
unable to prove the FPT-membership of PAV-Multiwinner with respect to $d$, but
we show that combining $d$ and $\triangle_{\text{V}}$ leads to an FPT-result.

We would like to point out that Misra, Nabeel, and Singh [58] studied
kernelization of MAV-Multiwinner with respect to the combined parameters $d+m$
and $n+k$, and showed that these problems do not admit any polynomial kernels
unless $\textsf{CoNP}\subseteq\textsf{NP}/\textsf{Poly}$444A kernelization
with respect to a parameter is a polynomial-time algorithm which transforms an
instance into an equivalent instance with the size of the main part being
bounded from above by a computable function of the parameter. See [23, Chapter
2] for more details.. In addition, Liu and Guo [54] studied the combined
parameter $k+n$ for some generalizations of MAV-Multiwinner. Betzler, Slinko,
and Uhlmann [5] proved that CCAV-Multiwinner is W[2]-hard with respect to the
combined parameter of $R=n-d$ and $k$. Though not explicitly stated, their
reduction actually implies that CCAV-Multiwinner does not admit any polynomial
kernel with respect to both $n$ and $m$, unless the polynomial hierarchy
collapses to the third level.555These kernelization lower bounds follow from a
reduction by Betzler, Slinko, and Uhlmann [5] and several techniques for
establishing kernelization lower bounds delineated in [23, Chapter 14] and
[25].

###  3.3 Structural Parameters

Heretofore, the most widely studied structural parameters in the setting of
multiwinner voting are based on various concepts of restricted preference
domains such as single-peaked preferences and single-crossing preferences
(see, e.g., [21]). Particularly, these parameters measure how far an election
is away from a specific domain of preferences. In this paper, we study two
structural parameters of incidence graphs of elections. Recall that the
incidence graph of an election $E=(C,V)$ is a bipartite graph $G_{E}$ with
vertex set $C\cup V$ so that there is an edge between a candidate $c\in C$ and
a vote $v\in V$ if and only if $c\in v$. We prove that CCAV-Multiwinner is FPT
with respect to treewidth of incidence graphs, and MAV-Multiwinner and PAV-
Multiwinner are FPT if we combine the treewidth and the parameter $k$. When
parameterized by the size of maximum matchings of incidence graphs, we have
FPT-algorithms for all three rules.

###  3.4 Other Related Works

In addition to the extensive effort made from the angle of parameterized
complexity, much exploration on the complexity of $\tau$-Multiwinner
restricted to preference domains has been pursued over the past few years.
Betzler, Slinko, and Uhlmann [5] developed polynomial-time algorithms for
CCAV-Multiwinner in the single-peaked domain. This algorithm was subsequently
extended to an FPT-algorithm with respect to the parameter single-peaked width
by Cornaz, Galand, and Spanjaard [21]. Yu, Chan, and Elkind [82] studied the
domain of single-peaked on trees, and obtained both polynomial-time algorithms
and NP-hardness results for many variants of CCAV. One of their results [82,
Theorem 4.1] is in essence an FPT-algorithm for CCAV-Multiwinner with respect
to the combined parameter $m+k+\lambda$, where $\lambda$ is the number of
leaves of the underlying tree. A follow-up paper by Peters and Elkind [60]
addressed several open questions left in [82]. Later, Elkind and Lackner [30]
proposed 13 different restricted domains of dichotomous preferences, and
obtained several polynomial-time algorithms and FPT-algorithms for
$\tau$-Multiwinner for $\tau$ being CCAV, MAV, and PAV with respect to the
parameter $\triangle_{\text{V}}$, and the combined parameter $k+d$, when the
given elections fall into certain specific categories of their proposed
domains. Liu and Guo [54] presented polynomial-time algorithms for MAV-
Multiwinner in two of the domains proposed by Elkind and Lackner. Peters and
Lackner [61] proposed the domain of single-peaked on a circle, an appealing
generalization of the single-peaked domain. They provided a polynomial-time
algorithm for CCAV-Multiwinner in this domain. Peters [59] observed a
relationship between voting problems restricted to the single-peaked domain
and totally unimodular integer linear programming. In view of this observation
and the fact that totally unimodular integer linear programming is polynomial-
time solvable [65], a variety of polynomial-time solvability results were
obtained, including one for PAV-Multiwinner.666We note that [61] integrates a
conference paper with the same title appeared in AAAI 2017 and [59]. Skowron
et al. [69] complemented these results by showing that CCAV-Multiwinner is
polynomial-time solvable restricted to the single-crossing domain. Clearwater,
Puppe, and Slinko [20] then extended this result to the domain of single-
crossing on trees. Yang [79] expanded several domains of Elkind and Lackner
[30] to directed tree-embedded domains, and derived a number of polynomial-
time algorithms for MAV-Multiwinner, CCAV-Multiwinner, and PAV-Multiwinner
restricted to these domains.

As traditional approaches tackling NP-hard problems, approximation and
heuristic algorithms for $\tau$-Multiwinner where
$\tau\in\\{\text{MAV},\text{CCAV},\text{PAV}\\}$ have also been perpetually
reported over the past few years [17, 24, 36, 66, 67].

We would like to mention that the (parameterized) complexity of
$\tau$-Multiwinner for numerous ranking-based multiwinner voting rules $\tau$
has been considerably studied in the literature, too [5, 33, 43]. On top of
that, the (parameterized) complexity of winner determination problems for
several variants of multiwinner voting rules has been explored recently [14,
76].

Finally, we remark that, besides winner determination problems, investigating
the complexity of many strategic voting problems, such as manipulation,
control, and bribery, has gained increasing interest in recent years as well
[15, 35, 77, 78]. We refer to [49] for a comprehensive survey of approval-
based multiwinner voting where many other important issues not discussed above
have been greatly elaborated on.

Table 1: A summary of the parameterized complexity of $\tau$-Multiwinner. Our
results are in boldface. Additionally, $\omega$ is the treewidth and $\alpha$
is the size of a maximum matching of the incidence graph of a given election.
Hardness results marked by the $\star$ symbol mean that they hold even if
every vote approves two candidates. Results without any marks mean that they
are either trivial or implied by other results in the table. Underlined FPT-
results mean that the corresponding problems do not admit any polynomial
kernels assuming certain standard complexity hypothesis.

| single parameters
---|---
| $d$ | $m$ | $n$ | $k$ | $\overline{k}$ | $(\triangle_{\text{V}},\triangle_{\text{C}})$
MAV | FPT [58] | FPT [58] | FPT [58] | W[2]-h [58] |  W[1]-h⋆ |  $(\geq 2,\geq 3)$: NP-h [51]
(Cor. 1) | others: P (Cor. 5, Thm. 4)
CCAV | $\mathbf{{2^{O(d)}}}$ | FPT [5] |  $\underline{n^{n}}$ [5] |  W[2]-h [5] |  W[1]-h⋆ |  $(\geq 2,\geq 3)$: NP-h [63]
(Cor. 2) |  $\mathbf{{2^{O(n)}}}$ (Cor. 3) |  W[1]-h⋆ (Thm. 7) | (Thm. 2) | others: P (Cor. 5, Thm. 4)
PAV | open | FPT | FPT |  |  W[1]-h⋆ |  $(\geq 2,\geq 3)$: NP-h [4]
(Thm. 1) |  W[1]-h⋆ [4] | (Thm. 3) |  $(\geq 3,2)$: open
|  |  | others: P (Cor. 5, Thm. 5)

| combined parameters | structural parameters
---|---|---
| $k+\triangle_{\text{C}}$ | $k+\triangle_{\text{V}}$ | $\overline{k}+\triangle_{\text{C}}$ | $\overline{k}+\triangle_{\text{V}}$ | $d+\triangle_{\text{V}}$ | $\omega$ | $\alpha$
MAV | FPT | FPT | FPT | W[1]-h⋆ | FPT | ${\omega}+k$ | FPT
(Thm. 6) | (Cor. 7) | (Thm. 8) |  FPT (Thm. 12) | (Thm. 13)
CCAV | FPT | W[1]-h⋆ | FPT | W[1]-h⋆ | FPT | $\mathbf{4}^{\omega}$ (Thm. 11) | $\mathbf{4}^{\alpha}$
(Cor. 6) | (Thm. 9)
PAV | $k+\triangle_{\text{C}}+\triangle_{\text{V}}$ | W[1]-h⋆ [4] | open | W[1]-h⋆ | FPT | $\omega+k$ | FPT
FPT (Cor. 8) | (Thm. 10) |  FPT (Thm. 12) | (Thm. 13)

##  4 Single Parameters

In this section, we investigate some predominant single parameters.

###  4.1 Parameters $d$, $n$, and $\overline{k}$

We start with an FPT-algorithm for PAV-Multiwinner with respect to $n$. Before
presenting our algorithm, let us recall the main idea of an FPT-algorithm for
MAV-Multiwinner with respect to $n$ [58]. First, the candidates are
partitioned into at most $2^{n}$ subsets, each consisting of all candidates
approved by exactly the same votes. Then, what matters for solving the problem
is only how many candidates from each subset are contained in a desired
$k$-committee. Based on this observation, MAV-Multiwinner can be reduced to
integer linear programming (ILP) by assigning to each subset defined above an
integer variable. As the number of variables is bounded by $2^{n}$, Lenstra’s
theorem [52] provides an FPT-algorithm for MAV-Multiwinner with respect to
$n$. Although the FPT-algorithm with respect to $n$ for CCAV-Multiwinner
derived by Betzler, Slinko, and Uhlmann [5] is not ILP-based, it is easy to
see that CCAV-Multiwinner also admits a similar ILP formulation.
Unfortunately, this framework does not apply to PAV-Multiwinner. The reason is
that the objective in this case is a nonlinear function. To overcome this
obstacle, we resort to an FPT-framework proposed by Bredereck et al. [16] for
the Mixed Integer Programming With Simple Piecewise Linear Transformations
problem. In fact, we need only a special case of the problem defined below.
For a vector $x\in\mathbb{Z}^{p}$ and an integer $i\in[p]$, we use $x_{i}$ to
denote the $i$-th component of $x$.

A real-valued function $f$ is concave if for every $x$ and $y$ such that $x<y$
and every $\lambda$ such that $0\leq\lambda\leq 1$ it holds that

$f(\lambda\cdot x+(1-\lambda)\cdot y)\geq\lambda\cdot f(x)+(1-\lambda)\cdot
f(y).$

Intuitively, a function is concave if for every $x$, $y$, and $z$ such that
$x\leq y\leq z$, the point $(y,f(y))$ is not below the straight line
determined by the two points $(x,f(x))$ and $(z,f(z))$. A piecewise linear
concave function is a piecewise linear function that is concave.

Integer Programming With Simple Piecewise Linear Transformations (IPWSPLT)
---
Input: |  A collection $\\{f_{i,j}:i\in[p],j\in[q]\\}$ of $p\cdot q$ piecewise linear concave functions, and a vector $b\in\mathbb{Z}^{p}$.
Question: |  Is there a vector $x\in\mathbb{Z}^{q}$ such that for every $i\in[p]$ it holds that $\sum_{j=1}^{q}f_{i,j}(x_{j})\leq b_{i}?$ (1)

The original problem MIPWSPLT studied by Bredereck et al. [16] is more general
in that it allows the existence of additional variables which may take
nonintegral values, and allows the occurrences of both piecewise linear
concave functions and piecewise linear convex functions simultaneously.

######  Lemma 1 ([16]).

_IPWSPLT_ can be solved in time $O({\emph{{poly}}}(|I|,t)\cdot
q^{2.5q+o(q)})$, where $|I|$ is the number of bits encoding the input, and $t$
is the maximum number of pieces per function.

We note that Lemma 1 still holds if in the definition of IPWSPLT the less than
sign is replaced with the greater than sign or the equal sign in (1) for
several $i\in[p]$ [16].

Now we are ready to present our FPT-algorithm for PAV-Multiwinner with respect
to $n$. We provide indeed an algorithm for a more general problem called
Annotated PAV-Multiwinner. In this problem, we are given an election $(C,V)$,
a subset $C^{\prime}\subseteq C$ of candidates, an integer $k$ such that
$|C^{\prime}|\leq k\leq|C|$, and a number $d$, and the question is whether
there is a $k$-committee $w\subseteq C$ such that $C^{\prime}\subseteq
w\subseteq C$ and PAV$(V,w)\geq d$. Clearly, PAV-Multiwinner is a special case
of Annotated PAV-Multiwinner where $C^{\prime}=\emptyset$. This generalization
is afterward exploited in an algorithm presented in Section 6.

Figure 1: An illustration of the piecewise linear concave function $f$ in the
proof of Theorem 1.

######  Theorem 1.

Annotated PAV-Multiwinner is _FPT_ with respect to $n$.

Proof We prove Theorem 1 by reducing Annotated PAV-Multiwinner to IPWSPLT.

Let $I=(E,C^{\prime},k,d)$ be an instance of Annotated PAV-Multiwinner, where
$E=(C,V)$ and $C^{\prime}\subseteq C$. Let $n=|V|$ be the number of votes. In
what follows, we construct an integer programming formulation of Annotated
PAV-Multiwinner, prove the correctness of the reduction, and prove that the
formulation is an instance of IPWSPLT. We create two types of variables.
First, we create a variable $x_{v}$ for each vote $v\in V$, indicating the
number of $v$’s approved candidates in a desired $k$-committee. Second, for
each $U\subseteq V$, let $C_{U}$ be the set of candidates approved by all
votes in $U$ but disapproved by votes from $V\setminus U$, i.e.,
$C_{U}=\\{c\in C:V(c)=U\\}$. We create a variable $x_{U}$ for each $U\subseteq
V$ which indicates the number of candidates from $C_{U}$ that are supposed to
be in a desired $k$-committee. The constraints are as follows.

  1. (1)

For each variable $x_{U}$, $U\subseteq V$, it holds that $|C^{\prime}\cap
C_{U}|\leq x_{U}\leq|C_{U}|$.

  2. (2)

For each $v\in V$, we have $x_{v}=\sum_{v\in U\subseteq V}x_{U}$.

  3. (3)

As we aim to select a committee of cardinality $k$, we have $\sum_{U\subseteq
V}x_{U}=k$.

  4. (4)

For the last constraint, we need to define a piecewise linear concave function
$f:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ as follows. First,
$f(0)=0$. Second, for each positive integer $x$, we define
$f(x)=\sum_{i=1}^{x}\frac{1}{i}$. Third, for each real $x$ such that $y<x<y+1$
and $y$ is a nonnegative integer, we define

$f(x)=f(y)+(x-y)\cdot(f(y+1)-f(y)).$

Figure 1 illustrates the function $f$.

The last constraint is then $\sum_{v\in V}f(x_{v})\geq d$, which ensures that
the desired $k$-committee has PAV score at least $d$.

Now we show the correctness of the reduction, i.e., we show that the given
instance $I$ is a Yes-instance if and only if the above integer programming
has a feasible solution.

$(\Rightarrow)$ Assume that $I$ is a Yes-instance, i.e., there exists a
$k$-committee $w$ so that $C^{\prime}\subseteq w\subseteq C$ and
$\textsf{PAV}(V,w)\geq d$. We assign to the variables constructed above the
corresponding values, i.e., we let $x_{U}=|w\cap C_{U}|$ for each $U\subseteq
V$, and let $x_{v}=|v\cap w|$ for each $v\in V$. Obviously, $|w\cap
C_{U}|\leq|C_{U}|$. As $C^{\prime}\subseteq w$, it holds that $|C^{\prime}\cap
C_{U}|\leq|w\cap C_{U}|$. Therefore, constraints defined in (1) hold. As for
every two distinct $U,U^{\prime}\subseteq V$, $C_{U}$ and $C_{U^{\prime}}$ are
disjoint and, moreover, $\bigcup_{{U}\subseteq V}C_{{U}}=C$, it holds that

$|v\cap w|=\sum_{v\in U\subseteq V}|v\cap w\cap C_{U}|=\sum_{v\in U\subseteq
V}|w\cap C_{U}|=\sum_{v\in U\subseteq V}x_{U}$ (2)

for all $v\in V$, and $\sum_{U\subseteq V}|w\cap C_{U}|=|w|=k$. In other
words, all constraints described in (2)–(3) are satisfied. Notice that by the
definition of $C_{U}$, if $v\not\in U$ then $C_{U}\cap v=\emptyset$, and if
$v\in U$ then $C_{U}\subseteq v$. This ensures the correctness of Equality
(2). Finally, the constraint given in (4) holds because $\sum_{v\in
V}f(x_{v})$ is exactly the PAV score of $w$ with respect to $V$ which is equal
to or greater than $d$.

$(\Leftarrow)$ Assume that the above integer programming has a feasible
solution. We show below that $I$ is a Yes-instance by constructing a desired
$k$-committee $w$. Initially, let $w=\emptyset$. For every $x_{U}$,
$U\subseteq V$, in the feasible solution, we arbitrarily select $x_{U}$
candidates from $C_{U}$ so that all candidates in $C^{\prime}\cap C_{U}$ are
selected, and add them into $w$. By the constraints in (1), these $x_{U}$
candidates exist for each $U\subseteq V$. By the constraint in (3), we know
that $w$ consists of $k$ candidates. By the constraints in (2), $x_{v}$ is
exactly the number of candidates from $w$ approved in $v$. As a result,
$\sum_{v\in V}f(x_{v})$ is exactly the PAV score of $w$ with respect to $V$.
Then, from the constraint in (4), it follows that $\textsf{PAV}(V,w)\geq d$.
Finally, as $\bigcup_{U\subseteq V}C_{U}=C$, by the definition of $w$ we know
that $C^{\prime}$ is contained in $w$. Now we can conclude that $I$ is a Yes-
instance of Annotated PAV-Multiwinner.

Next, we show that the above integer programming is an instance of IPWSPLT. To
this end, we reiterate that IPWSPLT contains ILP as a special case.
Constraints described in (1)–(3) are standard constraints (or can be
transformed into standard form trivially) of ILP. It is easy to see that the
function $f$ defined in (4) is a piecewise linear concave function. Therefore,
the above integer programming is an instance of IPWSPLT.

It remains to analyze the running time of the algorithm. The above reduction
clearly takes FPT-time in $n$, and the number of variables is $n+2^{n}$. Then,
by Lemma 1 and the correctness of the reduction, Annotated PAV-Multiwinner is
FPT with respect to $n$. ∎

We note that a similar FPT-algorithm for winners computation for a large class
of ranking-based multiwinner voting rules has been also derived by Faliszewski
et al. [33, Theorem 16].

Now we study the parameter $\overline{k}=m-k$, i.e., the number of candidates
not in a desired $k$-committee. In regard to MAV, the NP-hardness proof by
LeGrand [51] actually already implied that MAV-Multiwinner is W[1]-hard with
respect to $\overline{k}$. Precisely, LeGrand’s NP-hardness reduction is from
the Vertex Cover problem, where vertices correspond to candidates, and edges
correspond to votes so that each vote approves exactly the candidates
corresponding to its two endpoints. It is easy to see that there is a vertex
cover of cardinality $\kappa$ if and only if there is a $\kappa$-committee so
that the Hamming distance between this committee and each vote is at most
$\kappa$. The W[1]-hardness of MAV-Multiwinner follows from that Vertex Cover
is W[1]-hard with respect to $m-\kappa$ where $m$ is the number of vertices
(candidates) [27].

######  Corollary 1 ([27, 51]).

MAV-Multiwinner is _W[1] -hard_ with respect to $\overline{k}$ even when every
vote approves two candidates.

It should be noted that Vertex Cover with respect to $m-\kappa$ is exactly a
parameterized variant of the Independent Set problem. We provide the formal
definition of the problem below because it will be used to establish our next
intractability result.

An independent set of a graph is a subset of pairwise nonadjacent vertices.

$\kappa$-Independent Set ($\kappa$-IDS)
---
Input: |  A graph $G=(N,A)$ and an integer $\kappa$.
Parameter: |  $\kappa$.
Question: |  Does $G$ admit an independent set of cardinality at least $\kappa$?

######  Theorem 2.

CCAV-Multiwinner is _W[1] -hard_ with respect to $\overline{k}$, even when
every vote approves two candidates.

Proof To prove Theorem 2, we offer a reduction from $\kappa$-IDS to CCAV-
Multiwinner, similar to the one for MAV-Multiwinner discussed above by LeGrand
[51]. Let $(G=(N,A),\kappa)$ be an instance of $\kappa$-IDS. We construct an
instance $((C,V),k,d)$ of CCAV-Multiwinner as follows. For each vertex $c\in
N$, we create one candidate denoted by the same symbol for simplicity. Let
$C=N$ and let $m=|C|$. For each edge $\\{c,c^{\prime}\\}\in A$, we create one
vote $v$ approving exactly $c$ and $c^{\prime}$, i.e., $v=\\{c,c^{\prime}\\}$.
Let $V$ be the set of the created votes. Finally, we set $\overline{k}=\kappa$
(hence $k=m-\kappa$) and set $d=|A|$.

The correctness of the reduction is easy to check. If there is an independent
set $I$ of size $\overline{k}$, the CCAV score of the
$(m-\overline{k})$-committee $N\setminus I$ is $d$. Conversely, if there is an
$(m-\overline{k})$-committee $w$ of CCAV score $d$, every vote has at least
one of its approved candidates in the committee. Due to the construction, this
implies that $N\setminus w$ is an independent set. ∎

For PAV, we also obtain a W[1]-hardness result via a reduction from the
following problem.

Minimum ($\kappa$)-Vertex Subgraph ($\kappa$-MVS)
---
Input: |  A graph $G=(N,A)$ and two integers $\kappa$ and $\ell$.
Parameter: |  $\kappa$.
Question: |  Is there $S\subseteq N$ such that $|S|=\kappa$ and $G[N\setminus S]$ has at most $\ell$ edges?

Cai [18] proved that the $\kappa$-MVS problem is W[1]-hard even when the input
graph is regular, i.e., all vertices have the same degree.

######  Theorem 3.

PAV-Multiwinner is _W[1] -hard_ with respect to $\overline{k}$, even when
every vote approves two candidates.

Proof We provide a reduction from $\kappa$-MVS to PAV-Multiwinner. Let
$(G,\kappa,\ell)$ be an instance of $\kappa$-MVS such that every vertex of $G$
has degree $r$ for some positive integer $r$. Let $G=(N,A)$ and let $m=|N|$.
Without loss of generality, we assume that $\kappa<m$. We construct an
instance $((C,V),k,d)$ of PAV-Multiwinner as follows. For each vertex $c\in
N$, we create one candidate in $C$ denoted by the same symbol, and for each
edge $\\{c,c^{\prime}\\}\in A$, we create one vote approving $c$ and
$c^{\prime}$ in $V$. We set $k=m-\kappa$, and hence $\overline{k}=\kappa$.
Finally, we set $d=(m-\kappa)\cdot r-\frac{\ell}{2}$. It remains to show the
correctness.

$(\Rightarrow)$ Suppose that there exists $S\subseteq N$ so that $|S|=\kappa$
and $G[N\setminus S]$ contains exactly $\ell^{\prime}\leq\ell$ edges. Then the
PAV score of the committee $N\setminus S$ is

$\frac{3}{2}\ell^{\prime}+\left((m-\kappa)\cdot
r-2\ell^{\prime}\right)=(m-\kappa)\cdot r-\frac{\ell^{\prime}}{2}\geq d.$

Obviously, $|N\setminus S|=m-|S|=k$. Therefore, the PAV-Multiwinner instance
is a Yes-instance.

$(\Leftarrow)$ Conversely, suppose that $w\subseteq C$ is an
$(m-\kappa)$-committee of PAV score at least $d$. Let $\ell^{\prime}$ be the
number of votes whose both approved candidates are in $w$. Due to the
reduction, every candidate is approved by exactly $r$ votes. Therefore, there
are exactly $(m-\kappa)\cdot r-2\ell^{\prime}$ votes which have exactly one of
their approved candidates in $w$. Hence, the PAV score of $w$ is
$\frac{3}{2}\ell^{\prime}+((m-\kappa)\cdot r-2\ell^{\prime})$, which is at
least $d$. It immediately follows that $\ell^{\prime}\leq\ell$, implying that
$N\setminus w$ is a Yes-witness of the $\kappa$-MVS instance
$(G,\kappa,\ell)$. ∎

It should be pointed out that a reduction established by Skowron, Faliszewski,
and Lang [68, Theorem 5] for showing NP-hardness of a related problem also
implies that PAV-Multiwinner is W[1]-hard with respect to
$\overline{k}$.777Their reduction is from Vertex Cover restricted to
$3$-regular graphs, and a slight modification results in a reduction based on
Vertex Cover restricted to regular graphs which is W[1]-hard parameterized by
$m-\kappa$ [27].

Now we move on to the parameter $d$. We observe that CCAV-Multiwinner is
equivalent to the Partial Hitting Set problem which has been intensively
studied in the literature.

Partial Hitting Set
---
Input: |  A universe $U$, a collection $\mathcal{S}$ of subsets of $U$, and two nonnegative integers $a$ and $b$.
Parameter: |  $b$.
Question: |  Is there $S\subseteq U$ such that $|S|=a$ and $S$ intersects at least $b$ elements of $\mathcal{S}$?

Clearly, by taking $C=U$, $V=\mathcal{S}$, $k=a$, and $d=b$ in the above
definition we obtain CCAV-Multiwinner. Bläser [6] derived an algorithm running
in time $O^{*}(2^{O(b)})$ for Partial Hitting Set. This leads to the following
corollary.

######  Corollary 2 ([6]).

CCAV-Multiwinner can be solved in time $O^{*}(2^{O(d)})$.

Observe that every CCAV-Multiwinner instance where $d>n$ is a No-instance. As
a result, Corollary 2 implies an algorithm for CCAV-Multiwinner running in
time $O^{*}(2^{O(n)})$, which appreciably improves the $O^{*}(n^{n})$
algorithm presented in [5].

######  Corollary 3 ([6]).

CCAV-Multiwinner can be solved in time $O^{*}(2^{O(n)})$.

Bläser [6] also presented a randomized algorithm of running time
$O^{*}((2e)^{b})$ which solves the Partial Hitting Set problem correctly with
probability at least $1-e^{-1}$, where $e$ is the Napier’s constant. We arrive
at the following corollary.

######  Corollary 4 ([6]).

There is a randomized algorithm running in time $O^{*}((2e)^{d})$ which solves
CCAV-Multiwinner correctly with probability at least $1-e^{-1}$.

###  4.2 Parameters $\triangle_{\text{V}}$ and $\triangle_{\text{C}}$

In this section, we study the two parameters $\triangle_{\text{V}}$ and
$\triangle_{\text{C}}$. First, as Vertex Cover remains NP-hard when restricted
to cubic graphs (i.e., $3$-regular graphs) [39], the reduction for the NP-
hardness of MAV-Multiwinner established by LeGrand [51] implies that MAV-
Multiwinner is NP-hard even when every candidate is approved by three votes
and every vote approves two candidates. It remains to study the cases where
$\triangle_{\text{V}}\leq 1$ or $\triangle_{\text{C}}\leq 2$.

Recall that for a committee selection rule $\tau$ and an election $E=(C,V)$,
${\tau}(E,k)$ is the set of all optimal $k$-committees under $\tau$. More
precisely, for $\tau$ being MAV, $\tau(E,k)$ consists of all $k$-committees of
$C$ with the minimum Hamming distance to the votes, and for $\tau$ being CCAV
and PAV, ${\tau}(E,k)$ consists of all $k$-committees of $C$ with the maximum
CCAV and PAV scores, respectively.

It is easy to see that every election $E=(C,V)$ where every vote approves only
one candidate admits a $k$-committee, $k\leq|C|$, which is optimal with
respect to MAV, CCAV, and PAV at the same time. In fact, any optimal
$k$-committee under the approval voting (AV) is such a $k$-committee. The AV
score of a candidate $c$ is $|V(c)|$, the number of votes approving $c$, and
AV selects $k$-committees with the maximum sum of AV scores of candidates in
the committees.

######  Observation 1.

Let $E=(C,V)$ be an election where every vote in $V$ approves at most one
candidate, and let $k\leq|C|$ be an integer. It holds that _AV_
$(E,k)\subseteq{\emph{\text{MAV}}}(E,k)$ and
${\emph{\text{AV}}}(E,k)={\emph{\text{CCAV}}}(E,k)={\emph{\text{PAV}}}(E,k)$.

To see that ${\text{AV}}(E,k)\subseteq{\text{MAV}}(E,k)$ instead of
$\text{AV}(E,k)={\text{MAV}}(E,k)$ in Observation 1, consider an election with
two candidates $a$ and $b$, where $a$ is approved by two votes, and $b$ is
approved by a third vote which does not approve $a$. For $k=1$, both $\\{a\\}$
and $\\{b\\}$ are optimal with respect to MAV, but only $\\{a\\}$ is optimal
with respect to AV.

The following corollary follows from Observation 1 and the clear fact that an
optimal $k$-committee with respect to AV can be computed in polynomial time.

######  Corollary 5.

For each
$\tau\in\\{{\emph{\text{MAV}}},{\emph{\text{CCAV}}},{\emph{\text{PAV}}}\\}$,
$\tau$-Multiwinner is polynomial-time solvable when
$\triangle_{\emph{\text{V}}}\leq 1$.

Regarding $\triangle_{\text{C}}$, we have several polynomial-time solvability
results for $\triangle_{\text{C}}\leq 2$. One of our results is based on the
following polynomial-time solvable problem [53].

Simple $b$-Edge Cover of Multigraphs (SECM)
---
Input: |  A multigraph $G=(N,A)$, a function $f:N\rightarrow\mathbb{Z}^{+}$, and an integer $\kappa$.
Question: |  Is there $A^{\prime}\subseteq A$ such that $|A^{\prime}|\leq\kappa$ and every $v\in N$ is incident to at least $f(v)$ edges in $A^{\prime}$?

If we require $|A^{\prime}|=\kappa$ in the above definition, we obtain the
exact version of SECM (E-SECM). Clearly, E-SECM can also be solved in
polynomial time.

Every election $E=(C,V)$ can be represented by a multihypergraph where every
vote $v\in V$ is considered as a vertex and every candidate $c\in C$ is
considered as an edge consisting of vertices in $V(c)$. When a candidate is
approved by only one vote, there is a loop on this vote. We use $H(E)$ to
denote this multihypergraph representing $E$. Clearly, given an election, its
multihypergraph representation can be computed in polynomial time. When
$\triangle_{\text{C}}\leq 2$, $H(E)$ degenerates to a multigraph.

For a class $\mathcal{H}$ of multihypergraphs, we say that an election $E$ is
an $\mathcal{H}$-election if $H(E)\in\mathcal{H}$.

######  Theorem 4.

MAV-Multiwinner and CCAV-Multiwinner are polynomial-time solvable if
$\triangle_{\emph{\text{C}}}\leq 2$.

Proof We derive polynomial-time algorithms for the special cases of MAV-
Multiwinner and CCAV-Multiwinner stated in the theorem as follows. Let
$(E,k,d)$ be an instance of MAV-Multiwinner or CCAV-Multiwinner, where
$E=(C,V)$. We first compute the multigraph representation $H(E)=(V,A)$ of $E$
which can be done in polynomial time, where $A$ is the set of edges
corresponding to candidates in $C$.

MAV. We solve MAV-Multiwinner by reducing it to E-SECM. Recall that for each
$v\in V$, $|v|$ is the number of candidates approved by $v$ which is equal to
the number of edges incident to $v$ in $H(E)$. Observe that the Hamming
distance between every vote $v$ and every $k$-committee can be at most
$|v|+k$. Therefore, if $d\geq|v|+k$, we can safely remove $v$ from $V$ without
changing the answer to the instance. In light of this fact, we assume now that
$|v|+k>d$ for every $v\in V$. Let $f:V\rightarrow\mathbb{Z}^{+}$ be a function
such that $f(v)=\left\lceil\frac{|v|+k-d}{2}\right\rceil$ for every $v\in V$.
By setting $\kappa=k$ we complete the construction of an instance
$(H(E),f,\kappa)$ of E-SECM. Assume that there exists $A^{\prime}\subseteq A$
of cardinality $\kappa$ so that every $v\in V$ is incident to at least $f(v)$
edges in $A^{\prime}$. Let $w$ be the $k$-committee corresponding to
$A^{\prime}$. The Hamming distance between every vote $v\in V$ and $w$ is

$|v\setminus w|+|w\setminus v|\leq(|v|-f(v))+(k-f(v))\leq d.$

The proof for the other direction is analogous.

CCAV. We derive a greedy algorithm for CCAV-Multiwinner. Let $H^{\prime}$ be
the graph obtained from $H(E)$ by

  1. (1)

removing all loops, and

  2. (2)

for every two vertices between which there are multiple edges, removing all
but any arbitrary one of these multiple edges.

Let $M$ be a maximum matching of $H^{\prime}$, and let $V(M)$ be the set of
vertices saturated by $M$. We distinguish between two cases.

  * •

If $|M|\geq k$, we arbitrarily select $k$ edges in $M$, and let $w$ be the
$k$-committee corresponding to these selected edges.

  * •

If $|M|<k$, let $w$ be the set of candidates corresponding to edges in $M$.
Let $E^{\prime}$ be the election obtained from $E$ by removing all votes in
$V(M)$ and all candidates approved only by votes in $V(M)$. As $M$ is a
maximum matching of $H^{\prime}$, no two votes of $E^{\prime}$ approve a
common candidate. Then, for every nonempty vote in $E^{\prime}$, we
arbitrarily select one candidate approved by the vote. Let $w^{\prime}$ denote
the set of all these selected candidates. If $|w^{\prime}|\geq k-|M|$, we
include into $w$ any arbitrary $k-|M|$ candidates from $w^{\prime}$;
otherwise, we include into $w$ all candidates of $w^{\prime}$ together with
any arbitrary $k-|w\cup w^{\prime}|$ remaining candidates.

In either case, we conclude that the given instance of CCAV-Multiwinner is a
Yes-instance if and only if $\textsf{CCAV}(V,w)\geq d$. ∎

Now we study special cases of PAV-Multiwinner where $\triangle_{\text{C}}$ and
$\triangle_{\text{V}}$ are very small integers. We need the following notions.
A _path_ is a graph comprised of a sequence $v_{1}$, $v_{2}$, $\dots$, $v_{t}$
of $t$ vertices and $t-1$ edges so that there is an edge between two vertices
if and only if they are consecutive in the sequence. A _cycle_ is a graph
obtained from a path by adding an edge between the first and the last
vertices. A _hairstick_ is a graph obtained from a path by adding one loop
either on the first vertex or on the last vertex. A _double headed hairstick_
(DH-hairstick) is a graph obtained from a path by adding one loop on both the
first vertex and on the last vertex. We refer to Figure 2 for an illustration
of these graphs.

Figure 2: An illustration of cycles, paths, hairsticks, and DH-hairsticks.

######  Lemma 2.

Let $\mathcal{H}$ be the set of all paths, cycles, hairsticks, and DH-
hairsticks. Then, given an $\mathcal{H}$-election, we can compute a PAV
optimal $k$-committee of the election in polynomial time.

We defer the proof of Lemma 2 to the appendix.

######  Theorem 5.

PAV-Multiwinner is polynomial-time solvable if
$\triangle_{\emph{\text{C}}}\leq 1$ or
$\triangle_{\emph{\text{V}}}=\triangle_{\emph{\text{C}}}=2$.

Proof Let $I=(E,k,d)$ be an instance of PAV-Multiwinner where $E=(C,V)$.

We consider first the case where $\triangle_{\text{C}}\leq 1$. The following
algorithm finds an optimal $k$-committee. First, let $w=\emptyset$. Then, we
arrange votes in $V$ in a cyclic order (the relative orders of the votes do
not matter), and starting from any arbitrary vote we consider the votes one-
by-one in a clockwise order. In particular, if the currently considered vote
$v$ has at least one approved candidate not contained in $w$, i.e.,
$v\setminus w\neq\emptyset$, we add any arbitrary candidate from $v\setminus
w$ into $w$; otherwise we proceed to the next vote. The procedure runs until
$|w|=k$ or $w$ cannot be expanded in the way described above. Finally, we
conclude that $I$ is a Yes-instance if and only if $\textsf{PAV}(V,w)\geq d$.

Now we consider the case where $\triangle_{\text{C}}=\triangle_{\text{V}}=2$.
We first compute the multigraph representation $H(E)$ of $E$. Given a subgraph
of $H(E)$, the subelection of $E$ restricted to this subgraph refers to $E$
restricted to candidates and votes corresponding respectively to the edges and
the vertices of the subgraph. Observe that every connected component of $H(E)$
is either a path, a cycle, a hairstick, or a DH-hairstick, and by Lemma 2, for
every integer $j$, an optimal $j$-committee of each subelection restricted to
a connected component can be computed in polynomial time. Based on this, we
derive a dynamic programming algorithm. Precisely, let
$(H_{1},H_{2},\dots,H_{z})$ be an arbitrary order of the connected components
of $H(E)$. For each $i\in[z]$, let $m^{\leq i}$ be the number of edges in the
first $i$ connected components in the order. We maintain a table $T(i,j)$
where $i\in[z]$ and $j\leq\min\\{k,m^{\leq i}\\}$ is a nonnegative integer. We
define $T(i,j)$ as the PAV score of an optimal $j$-committee in the election
restricted to the first $i$ connected components. By Lemma 2, $T(1,j)$ for all
possible $j$ can be computed in polynomial time. We use the following
recursion to compute $T(i,j)$, assuming that all entries
$T(i^{\prime},j^{\prime})$ such that $i^{\prime}<i$ have been computed. For
each $j^{\prime}\leq j$, let $d(j^{\prime})$ be the PAV score of an optimal
$j^{\prime}$-committee of $E$ restricted to $H_{i}$, which can be computed in
polynomial time by Lemma 2. Then, we have that

$T(i,j)=\max_{\begin{subarray}{c}j^{\prime}\in[j]\cup\\{0\\},\\\
j-j^{\prime}\leq m^{\leq
i-1}\end{subarray}}\\{d(j^{\prime})+T(i-1,j-j^{\prime})\\}.$

After all entries are computed, we conclude that the given instance $I$ is a
Yes-instance if and only if $T(z,k)\geq d$. ∎

##  5 Combined Parameters

The study in the previous section revealed that the parameters $k$,
$\overline{k}$, $\triangle_{\text{V}}$, and $\triangle_{\text{C}}$ generally
lead to fixed-parameter intractability results. In this section, we explore
whether combining two or three of them offers us FPT-results.

###  5.1 Combining $k$ with $\triangle_{\text{V}}$ and $\triangle_{\text{C}}$

We first consider the combined parameter $k+\triangle_{\text{C}}$, starting
with an FPT-result for MAV-Multiwinner.

######  Theorem 6.

MAV-Multiwinner is _FPT_ with respect to $k+\triangle_{\emph{\text{C}}}$.

Proof We prove the theorem by giving an FPT-algorithm for MAV-Multiwinner as
follows. Let $I=(E,k,d)$ be an instance of MAV-Multiwinner, where $E=(C,V)$.
Let $n=|V|$. If $n\leq k\cdot\triangle_{\text{C}}+1$, then as MAV-Multiwinner
is FPT with respect to $n$ [58], we can solve $I$ in FPT-time in
$k+\triangle_{\text{C}}$. Otherwise, let $(v_{1},v_{2},\dots,v_{n})$ be a
linear order on $V$ such that $|v_{i}|\geq|v_{i+1}|$ for every $i\in[n-1]$,
i.e., $v_{i}$ approves at least the same number of candidates as $v_{i+1}$
does. Then, the algorithm deletes the last $n-(k\cdot\triangle_{\text{C}}+1)$
votes in this order, and solves the remaining instance by an FPT-algorithm
with respect to the number of votes (e.g., the one presented in [58]).

It remains to prove the correctness of the algorithm. Let $E^{\prime}$ be the
election after the deletion of the votes as described above. Clearly, every
$k$-committee of the original election with MAV score $d$ is a $k$-committee
of $E^{\prime}$ with MAV score at most $d$. To show the correctness for the
opposite direction, let $w$ be a $k$-committee of $E^{\prime}$ with MAV score
$d$. As every candidate is approved by at most $\triangle_{\text{C}}$ votes,
at most $k\cdot\triangle_{\text{C}}$ votes in $E^{\prime}$ intersect $w$. As
$E^{\prime}$ contains the first $k\cdot\triangle_{\text{C}}+1$ votes in the
order defined above, there exists $i\in[k\cdot\triangle_{\text{C}}+1]$ so that
the vote $v_{i}$ does not approve any candidate from $w$. The Hamming distance
between $w$ and $v_{i}$ is $k+|v_{i}|\leq d$. As $|v_{j}|\leq|v_{i}|$ for
every deleted vote $v_{j}$, $j\geq k\cdot\triangle_{\text{C}}+2$, the Hamming
distance between $w$ and $v_{j}$ is at most $k+|v_{j}|\leq k+|v_{i}|\leq d$.
It follows that $w$ has MAV score $d$ in the election $E$. ∎

Let us move on to CCAV. Obviously, if $w$ is a $k$-committee, then at most
$k\cdot\triangle_{\text{C}}$ votes intersect $w$. Hence, the CCAV score of
every optimal $k$-committee is bounded from above by
$k\cdot\triangle_{\text{C}}$. This observation leads to a simple algorithm for
CCAV-Multiwinner: if $d>k\cdot\triangle_{\text{C}}$, return “No”; otherwise,
solve it by Corollary 2 in time
$O^{*}(2^{O(d)})=O^{*}(2^{O(k\cdot\triangle_{\text{C}})})$.

######  Corollary 6.

CCAV-Multiwinner is _FPT_ with respect to $k+\triangle_{\emph{\text{C}}}$.

Now we study the combined parameter $k+\triangle_{\text{V}}$. Observe that
MAV-Multiwinner admits a straightforward FPT-algorithm with respect to
$k+\triangle_{\text{V}}$: if $d>k+\triangle_{\text{V}}$, every $k$-committee
has MAV score at most $d$, and hence we directly conclude that the given
instance is a Yes-instance; otherwise, we solve it by the FPT-algorithm with
respect to $d$ proposed in [58].

######  Corollary 7.

MAV-Multiwinner is _FPT_ with respect to $k+\triangle_{\emph{\text{V}}}$.

Aziz et al. [4] proved that PAV-Multiwinner is W[1]-hard when the parameter is
$k$ even if $\triangle_{\text{V}}=2$. This implies that PAV-Multiwinner is
W[1]-hard with respect to $k+\triangle_{\text{V}}$. For CCAV, Betzler, Slinko,
and Uhlmann [5] proved that CCAV-Multiwinner is W[2]-hard with respect to $k$
by a reduction from the Hitting Set problem. However, in the reduction the
maximum number of candidates approved by a vote is not bounded from above by a
constant. Using a reduction from the Partial Vertex Cover problem, we show
that CCAV-Multiwinner is W[1]-hard with respect to $k$ in this special case.

Partial Vertex Cover (PVC)
---
Input: |  A graph $G$ and two integers $\kappa$ and $\ell$.
Parameter: |  $\kappa$.
Question: |  Is there a subset $S\subseteq V(G)$ such that $|S|=\kappa$ and $S$ covers at least $\ell$ edges of $G$?

It is known that PVC is W[1]-hard with respect to $\kappa$ [42].

######  Theorem 7.

CCAV-Multiwinner is _W[1] -hard_ with respect to $k$ even if every vote
approves two candidates.

Proof Given an instance $(G,\kappa,\ell)$ of PVC, we create a CCAV-Multiwinner
instance as follows. We regard each vertex as a candidate and regard each edge
as a vote approving exactly the two candidates corresponding to its two
endpoints. The reduction is completed by setting $k=\kappa$ and $d=\ell$. The
correctness is easy to see. ∎

###  5.2 Combining $\overline{k}$ with $\triangle_{\text{V}}$ and
$\triangle_{\text{C}}$

We have shown that MAV-Multiwinner, CCAV-Multiwinner, and PAV-Multiwinner are
W[1]-hard or W[2]-hard with respect to the single parameter $\overline{k}$
even when $\triangle_{\text{V}}=2$. It follows that these problems are
W[1]-hard or W[2]-hard when parameterized by
$\overline{k}+\triangle_{\text{V}}$. Hence, we focus only on the combined
parameter $\overline{k}+\triangle_{\text{C}}$. We first prove that MAV-
Multiwinner is FPT with respect to this parameter by reducing it to an FPT
problem which is a generalization of the $r$-Set Packing problem.

Generalized $r$-Set Packing (G$r$SP)
---
Input: |  A universe $U$, a multiset $\mathcal{S}$ of $r$-subsets of $U$, a function $f:U\rightarrow\mathbb{N}_{0}$, and an integer $\kappa$.
Parameter: |  $\kappa+r$.
Question: |  Is there an $S\subseteq\mathcal{S}$ such that $|S|=\kappa$ and every $u\in U$ occurs in at most $f(u)$ elements of $S$?

It is known that G$r$SP is FPT [80]888The definition of G$r$SP in [80]
requests $f(u)$ to be positive for all $u\in U$. However, it is fairly easy to
see that if we allow $f(u)=0$ for some $u\in U$, we can safely remove all
$X\in\mathcal{S}$ such that $u\in X$ from the instance without changing the
answer to the instance. So, allowing $f(u)=0$ for $u\in U$ does not destroy
the fixed-parameter tractability of the problem.. It is easy to verify that
the variant of the G$r$SP problem where each $s\in\mathcal{S}$ is of
cardinality at most $r$, instead of exactly $r$, is reducible to G$r$SP in
polynomial time: for each $s\in\mathcal{S}$ such that $|s|<r$, create $r-|s|$
new elements in $U$, add them into $s$, and set $f(u)=1$ for every newly
introduced element in $U$. Therefore, the above variant is also FPT. In the
following, we use G$r_{\leq}$SP to denote this variant.

######  Theorem 8.

MAV-Multiwinner is _FPT_ with respect to
$\overline{k}+\triangle_{\emph{\text{C}}}$.

Proof Let $I=(E,k,d)$ be an instance of MAV-Multiwinner, where $E=(C,V)$. Note
that the Hamming distance between each vote $v$ and each $k$-committee is at
least $|k-|v||$. Therefore, if there exists a vote $v\in V$ such that $|v|<k$
and $d<k-|v|$, we immediately conclude that the given instance $I$ is a No-
instance. In what follows, we assume that for all $v\in V$ either it holds
that $|v|\geq k$, or it holds that $|v|<k$ and $d\geq k-|v|$. We reduce $I$ to
an instance of G$r_{\leq}$SP in polynomial time as follows. Precisely, let
$U=V$, and let $\mathcal{S}=\\{V(c):c\in C\\}$. Clearly, each element of
$\mathcal{S}$ is of cardinality at most $\triangle_{\text{C}}$. Hence, we set
$r=\triangle_{\text{C}}$. Regarding the function $f$, for each $v\in V$ we
define

$f(v)=\left\lfloor\frac{d+|v|-k}{2}\right\rfloor.$

By the above assumption, the function $f$ is nonnegative. Finally, we define
$\kappa=\overline{k}=|C|-k$.

It remains to prove that the two instances are equivalent.

$(\Rightarrow)$ Suppose that the G$r_{\leq}$SP instance is a Yes-instance. In
particular, let $S\subseteq\mathcal{S}$ be such that $|S|=\kappa$ and every
$u\in U$ occurs in at most $f(u)$ elements of $S$. Let $C^{\prime}$ be the
subset of candidates corresponding to $S$. Clearly,
$|C^{\prime}|=|S|=\overline{k}$. We claim that $w=C\setminus C^{\prime}$ is a
$k$-committee with MAV score at most $d$. Due to the above construction, every
vote $v$ occurs in at most $f(v)$ submultisets from $S$. This implies that $v$
has at least $|v|-f(v)$ of its approved candidates in $w$. Hence, the Hamming
distance between $v$ and $w$ is at most

$f(v)+(k-(|v|-f(v)))=2\cdot f(v)+k-|v|\leq d.$

In other words, the instance $I$ is a Yes-instance.

$(\Leftarrow)$ Suppose that $I$ is a Yes-instance, i.e., there is a
$k$-committee $w\subseteq C$ such that $\textsf{MAV}(V,w)\leq d$. Let
$C^{\prime}=C\setminus w$ and let $S=\\{V(c):c\in C^{\prime}\\}$. Then, for
each vote $v\in V$ at least $\left\lceil\frac{|v|+k-d}{2}\right\rceil$ of its
approved candidates must be in $w$. In other words, at most
$|v|-\left\lceil\frac{|v|+k-d}{2}\right\rceil=f(v)$ of $v$’s approved
candidates can be in $S$. This implies that the G$r_{\leq}$SP instance is a
Yes-instance. ∎

Next, we prove that CCAV-Multiwinner is FPT with respect to the combined
parameter $\overline{k}+\triangle_{\text{C}}$ as well.

######  Theorem 9.

CCAV-Multiwinner is _FPT_ with respect to
$\overline{k}+\triangle_{\emph{\text{C}}}$.

Proof We prove Theorem 9 by deriving a branch-and-bound FPT-algorithm with
respect to $\overline{k}+\triangle_{\text{C}}$. Let $I=((C,V),k,d)$ be an
instance of CCAV-Multiwinner. Throughout the algorithm, let
$\overline{k}=|C|-k$.

We first remove from $C$ all candidates not approved by any votes, and remove
from $V$ all empty votes. Then, we assume that neither of $C$ and $V$ is
empty, since otherwise the instance can be solved trivially. Observe now that
if a vote $v\in V$ approves more than $\overline{k}$ candidates, any
$k$-committee intersects $v$. In light of this observation, we need only to
focus on votes approving at most $\overline{k}$ candidates. Let $U\subseteq V$
be the submultiset of votes from $V$ approving at most $\overline{k}$
candidates. Let $B=\cup_{v\in U}v$ be the set of candidates approved by votes
from $U$. If $U=\emptyset$ or $|B|\leq k$, any $k$-committee containing $B$
satisfies all votes. In this case, we conclude that $I$ is a Yes-instance if
and only if $d\leq|V|$. Assume now that $|B|\geq k+1$. For each candidate
$c\in C$, let $V^{1}(c)$ be the multiset of votes in $U$ that approve $c$
only, i.e., $V^{1}(c)=\\{v\in U:v=\\{c\\}\\}$. Let $c^{\star}\in B$ be such
that $|V^{1}(c^{\star})|\leq|V^{1}(c)|$ for all $c\in B$. Let $A=\bigcup_{v\in
V(c)\cap U}v$. A significant observation is that there is an optimal
$k$-committee which does not contain $A$. (A proof for the observation is
given later.) In line with this observation, we solve the instance by
branching on which candidate from $A$ is not contained in a certain optimal
$k$-committee. In particular, we create $|A|$ branching cases, one for each
$x\in A$. In the branching case for $x\in A$, we reset $C\coloneqq
C\setminus\\{x\\}$ (which implies that $\overline{k}$ is decreased by one),
$d\coloneqq d-|V\setminus U|$, and $V\coloneqq U$, and solve the subinstance
iteratively by the above procedure. We use two pruning criteria to determine
when to terminate the branching: $d\leq 0$ or $\overline{k}=0$. When we arrive
at a branching node where $d\leq 0$ and $\overline{k}\geq 0$, it holds clearly
that the given instance $I$ is a Yes-instance, and thus in this case we
terminate the whole algorithm by returning “Yes”. When we arrive at a
branching node where $\overline{k}=0$ and $d>0$, we determine that $I$ is a
Yes-instance if $\textsf{CCAV}(V,C)\geq d$, and discard the corresponding
branching case otherwise.

Now we prove the correctness of the above mentioned observation. To this end,
assume that $w$ is an optimal $k$-committee such that $A\subseteq w$. Then, we
can obtain another optimal $k$-committee from $w$ by replacing $c^{\star}$
(notice that $c^{\star}\in A$) with any arbitrary candidate from $B\setminus
w$ (as $|B|\geq k+1$ such a candidate exists). The reason is that every vote
from $(V(c^{\star})\cap U)\setminus V^{1}(c^{\star})$ approves at least one
candidate from $w\setminus\\{c^{\star}\\}$ (because $A\subseteq w$). Hence,
removing $c^{\star}$ from $w$ may only affect the existence of representatives
of votes from $V^{1}(c^{\star})$ in the committee. However, as
$|V^{1}(c^{\star})|\leq|V^{1}(c)|$ for all $c\in B$, adding any arbitrary
candidate from $B\setminus w$ into $w$ makes all votes from $V^{1}(c^{\star})$
which do not have any representatives before have representatives now.

Regarding the running time of the algorithm, note that
$|A|\leq\triangle_{\text{C}}\cdot\overline{k}$. Hence, each branching node has
at most $\triangle_{\text{C}}\cdot\overline{k}$ children, implying that the
branching algorithm has running time
$O^{*}((\triangle_{\text{C}}\cdot\overline{k})^{\overline{k}})$. ∎

###  5.3 Combining $d$ and $\triangle_{\text{V}}$

It is known that MAV-Multiwinner and CCAV-Multiwinner are both FPT with
respect to the parameter $d$. However, it is unknown whether PAV-Multiwinner
is FPT with respect to $d$. Even though we are unable to resolve this open
question, we provide an FPT-algorithm when combining $d$ and
$\triangle_{\text{V}}$.

######  Theorem 10.

PAV-Multiwinner is _FPT_ with respect to $d+\triangle_{\emph{\text{V}}}$.

Proof We prove the theorem by giving a branch-and-bound FPT-algorithm. Let
$I=(E,k,d)$ be an instance of PAV-Multiwinner, where $E=(C,V)$.

First, if $C$ contains a candidate approved by at least $d$ votes in $V$, any
$k$-committee including this candidate is a desired committee. So, in this
case, we directly conclude that $I$ is a Yes-instance.

Second, let $C_{0}\subseteq C$ be the set of candidates not approved by any
votes in $V$. We remove from the election $(C,V)$ all candidates in $C_{0}$,
and reset $k\coloneqq\min\\{k,|C|\\}$. It is easy to verify that the two
instances before and after this step are equivalent. Afterwards, if $k=|C|$,
we conclude that $I$ is a Yes-instance if and only if $\textsf{PAV}(V,C)\geq
d$.

From now on, let us assume that every candidate is approved by at least one
and at most $d-1$ votes in $V$, and $k<|C|$. For each $S\subsetneq C$ and each
$c\in C\setminus S$, we define

$\Delta(S,c)=\textsf{PAV}(V,S\cup\\{c\\})-\textsf{PAV}(V,S),$

as the marginal contribution of $c$ to the PAV score of the committee
$S\cup\\{c\\}$. In our branching tree, each branching node is associated with
a subset $S\subsetneq C$ of cardinality at most $k$, which is supposed to be
contained in a desired committee. The root of the branching tree is associated
with $S=\emptyset$. Suppose we are now at a branching node associated with a
subset $S\subsetneq C$. Let $c\in C\setminus S$ be a candidate such that
$\Delta(S,c)\geq\Delta(S,c^{\prime})$ for all $c^{\prime}\in C\setminus S$.
Let $A=(\bigcup_{v\in V(c)}v)\setminus S$ be the set of candidates approved by
votes approving $c$ but not contained in $S$. Then, we create $|A|$ branching
cases, one for each $x\in A$. The set associated with the branching case for
$x\in A$ is $S\cup\\{x\\}$. The correctness of our branching is rooted in the
fact (a proof supporting this fact is provided later) that, if the given
instance $I$ is a Yes-instance, there exists at least one desired
$k$-committee which includes at least one candidate from $A$.

We terminate the branching when the branching depth of the current branching
node reaches $\min\\{k,d\cdot\triangle_{\text{V}}\\}$. Recall that the
branching depth of a branching node is the number of edges on the path from
the root to the node in the branching tree. By our branching strategy, the
branching depth of a branching node associated with $S$ is exactly $|S|$.
Therefore, when $k\leq d\cdot\triangle_{\text{V}}$ and the branching depth of
the current node associated with $S$ reaches $k$, we have that $|S|=k$. In
this case, if $S$ has PAV score at least $d$ with respect to $V$, we conclude
that the given instance $I$ is a Yes-instance. Consider now the case where
$k>d\cdot\triangle_{\text{V}}$. Note that
$\Delta(S,x)\geq\frac{1}{\triangle_{\text{V}}}$ for each possible $S$ and $x$.
Therefore, if the current branching node associated with $S$ has branching
depth $d\cdot\triangle_{\text{V}}$, $S$ is a $k^{\prime}$-committee,
$k^{\prime}\leq k$, of PAV score at least $d$. As a result, when
$k>d\cdot\triangle_{\text{V}}$ and the current node has branching depth
$d\cdot\triangle_{\text{V}}$, we directly conclude that $I$ is a Yes-instance.
If none of the branching nodes leads to a “Yes”-answer, we conclude that $I$
is a No-instance.

Note that $|A|\leq|V(c)|\cdot\triangle_{\text{V}}\leq
d\cdot\triangle_{\text{V}}$, where $A$ is as defined above. Therefore, the
running time of the whole algorithm is bounded by
$O^{*}((d\cdot\triangle_{\text{V}})^{d\cdot\triangle_{\text{V}}})$.

To show the correctness, it suffices to prove the following claim
(corresponding to the aforementioned fact).

######  Claim 1.

Let $S\subsetneq C$ be a subset of at most $k-1$ candidates, and let $c\in
C\setminus S$ be a candidate such that $\Delta(S,c)\geq\Delta(S,c^{\prime})$
for all $c^{\prime}\in C\setminus S$. Let $A=(\bigcup_{v\in V(c)}v)\setminus
S$. Then, if there is a $k$-committee $w\subsetneq C$ such that
${\emph{{PAV}}}(V,w)\geq d$, $S\subsetneq w$, and $A\cap w=\emptyset$, there
exists a $k$-committee $w^{\prime}\subsetneq C$ such that
${\emph{{PAV}}}(V,w^{\prime})\geq d$, $S\subseteq(w\cap w^{\prime})$, and
$A\cap w^{\prime}\neq\emptyset$.

Now we prove the claim. Let $S$, $c$, and $A$ be as stipulated in the claim.
Suppose that there is a $k$-committee $w\subsetneq C$ such that
${\textsf{PAV}}(V,w)\geq d$, $S\subsetneq w$, and $A\cap w=\emptyset$. Let
$c^{\prime}$ be any candidate in $w\setminus S$, and let
$w^{\prime}=w\setminus\\{c^{\prime}\\}\cup\\{c\\}$. Obviously,
$S\subseteq(w\cap w^{\prime})$ and $A\cap w^{\prime}\neq\emptyset$. To
complete the proof, it suffices to show that $\textsf{PAV}(V,w^{\prime})\geq
d$. First, as $w\cap A=\emptyset$ and $S\subseteq w$, it holds that
$\Delta(w,c)=\Delta(S,c)$. Second, as $S\subseteq w\setminus\\{c^{\prime}\\}$,
it holds that
$\Delta(w\setminus\\{c^{\prime}\\},c^{\prime})\leq\Delta(S,c^{\prime})$.
Third, it is clear that $\Delta(w\setminus\\{c^{\prime}\\},c)\geq\Delta(w,c)$.
We also reiterate that $\Delta(S,c)\geq\Delta(S,c^{\prime})$. Putting this all
together, we obtain
$\Delta(w\setminus\\{c^{\prime}\\},c)\geq\Delta(w\setminus\\{c^{\prime}\\},c^{\prime})$
which implies $\textsf{PAV}(V,w^{\prime})\geq{\textsf{PAV}}(V,w)\geq d$. The
proof is completed. ∎

We have derived many FPT-algorithms with respect to different single
parameters and their combinations. Our results reveal that MAV-Multiwinner and
CCAV-Multiwinner are FPT with respect to any combinations of three single
parameters studied so far. Unfortunately, we have only a few FPT-results for
PAV-Multiwinner even for combinations of two single parameters. We finish this
section by remarking that PAV-Multiwinner is FPT with respect to
$k+\triangle_{\text{V}}+\triangle_{\text{C}}$: if
$d>{k\cdot\triangle_{\text{C}}}$, return “No”; otherwise, solve the instance
in FPT-time via Theorem 10.

######  Corollary 8.

PAV-Multiwinner is _FPT_ with respect to
$k+\triangle_{\emph{\text{V}}}+\triangle_{\emph{\text{C}}}$.

##  6 Structural Parameters

In this section, we study two structural parameters of incidence graphs of
elections. For an election $E$, let $G_{E}$ denote the incidence graph of $E$.

###  6.1 Treewidth

Treewidth is a widely-studied notion to measure the closeness of a graph to a
tree [64]. It has been shown that a great deal of graphs stemming from
innumerable combinatorial problems in a variety of areas have bounded
treewidth (see, e.g., [48, 57, 72, 75]). Additionally, it has been scrutinized
that even when treewidth is large, using tree decompositions could also be
helpful for designing algorithms [56]. From a theoretical point of view, a
myriad of NP-hard problems are known to be FPT with respect to the parameter
treewidth [22]. With regard to the applicability of treewidth in multiwinner
voting, we point out that the treewidth of the incidence graph of an election
is no greater than the number $m$ of candidates and the number $n$ of voters
in the election, implying that any FPT-algorithm for $\tau$-Multiwinner with
respect to the treewidth also runs in FPT-time in $m$ and $n$.

A tree decomposition of a graph $G=(N,A)$ is a tuple $(T,\mathcal{B})$, where
$T=(L,F)$ is a rooted tree with vertex set $L$ and edge set $F$, and
$\mathcal{B}=\\{B_{x}\subseteq N:x\in L\\}$ is a collection of subsets of
vertices of $G$ such that the following three conditions are fulfilled
simultaneously:

  * •

For each vertex $v\in N$ in $G$ there exists at least one
$B_{x}\in\mathcal{B}$ such that $v\in B_{x}$, i.e., every vertex of $G$ is in
at least one element of $\mathcal{B}$.

  * •

For each edge $\\{v,u\\}\in A$ in $G$ there exists at least one
$B_{x}\in\mathcal{B}$ such that $v,u\in B_{x}$, i.e., every edge of $G$ is
contained in at least one element of $\mathcal{B}$.

  * •

If a vertex $v\in N$ is in $B_{x},B_{y}\in\mathcal{B}$, then $v$ is in every
$B_{z}\in\mathcal{B}$ where $z$ is a vertex on the unique path between $x$ and
$y$ in $T$.

The width of the tree decomposition is defined as
$\max_{B\in\mathcal{B}}{|B|-1}$. The treewidth of a graph $G$, denoted
$\omega(G)$, is the minimum possible width of tree decompositions of $G$.
Elements of $\mathcal{B}$ are called bags. To avoid confusion, in the
following we call vertices of $T$ nodes.

A more refined notion commonly used in designing FPT-algorithms is the so-
called nice tree decomposition [10]. In particular, a nice tree decomposition
$(T,\mathcal{B})$ of a graph $G$ is a tree decomposition of $G$ which further
satisfies the following conditions simultaneously:

  * •

Every bag $B\in\mathcal{B}$ associated with the root or a leaf of $T$ is
empty, i.e., $B_{x}=\emptyset$ if $x$ is the root or a leaf of $T$.

  * •

Nonleaf nodes of $T$ are categorized into introduce nodes, forget nodes, and
join nodes such that:

    * –

Each introduce node $x$ has exactly one child $y$ such that $B_{y}\subsetneq
B_{x}$ and $|B_{x}\setminus B_{y}|=1$, i.e., $B_{x}$ has exactly one more
element than $B_{y}$.

    * –

Each forget node $x$ has exactly one child $y$ such that $B_{x}\subsetneq
B_{y}$ and $|B_{y}\setminus B_{x}|=1$, i.e., $B_{x}$ is obtained from $B_{y}$
by removing one element.

    * –

Each join node $x$ has exactly two children $y$ and $z$ such that
$B_{x}=B_{y}=B_{z}$.

It is easy to see from the definition that in a nice tree decomposition, each
vertex can be introduced multiple times but can be only forgotten once.
Moreover, when a vertex is introduced in a bag $B_{x}$, all of its neighbors
contained in bags associated with nodes in the subtree rooted at $x$ are
contained in $B_{x}$.

######  Lemma 3 ([46]).

Let $G$ be a graph of $p$ vertices. Then, given a tree decomposition of $G$ of
width $\omega$, a nice tree decomposition of $G$ of width $\omega$ having
$O(p\cdot\omega)$ nodes can be computed in polynomial time.

It has long been known that calculating treewidth is NP-hard even for
bipartite graphs [8]. However, determining whether the treewidth of a graph is
at most $\omega$ is FPT with respect to $\omega$ and, moreover, powerful
heuristic and approximation algorithms for calculating treewidth have been
perpetually reported [7, 9, 73]. Besides, treewidth of chordal bipartite
graphs can be computed in polynomial time999A chordal bipartite graph is a
bipartite graph without induced cycles of length at least six., and the gap
between chordal bipartite graphs and general bipartite graphs is quite small
[47]. It is also well-known that every graph of $p$ vertices admits an optimal
tree decomposition of $O(p)$ nodes. Then, by Lemma 3, when we study FPT-
algorithms with respect to treewidth or a combined parameter involving
treewidth, it does not lose any generality to assume that a nice tree
decomposition is given.

######  Theorem 11.

CCAV-Multiwinner can be solved in time $O^{*}(4^{\omega})$ if a nice tree
decomposition of width $\omega$ and of $\emph{{poly}}(p)$ nodes of the
incidence graph of the input election is given, where $p$ is the number of
vertices of the incidence graph.

Proof Let $(E,k,d)$ be an instance of CCAV-Multiwinner where $E=(C,V)$ and
$k\leq|C|$. In addition, let $(T,\mathcal{B})$ be a nice tree decomposition of
$G_{E}$ of width $\omega$ that has $\textsf{poly}(p)$ nodes, where
$p=|C|+|V|$. We design a dynamic programming algorithm running in time
$O^{*}(4^{\omega})$ as follows.

For each bag $B_{x}\in\mathcal{B}$ associated with a node $x$ in the tree $T$,
let $C(B_{x})$ and $V(B_{x})$ be the set of candidate-vertices and the set of
vote-vertices contained in $B_{x}$, respectively. Moreover, let $C(T_{x})$ be
the set of candidates in bags associated with nodes in the subtree rooted at
$x$. Obviously, $C(B_{x})\subseteq C(T_{x})$. We maintain for each node $x$ in
$T$ a $3$-dimensional table $D_{x}(C^{\prime},V^{\prime},k^{\prime})$, where
$C^{\prime}$ is a subset of $C(B_{x})$ such that $|C^{\prime}|\leq k$,
$V^{\prime}$ is a submultiset of $V(B_{x})$, and $k^{\prime}$ is an integer
such that $|C^{\prime}|\leq k^{\prime}\leq\min\\{k,|C(T_{x})|\\}$. We say that
a $k^{\prime}$-committee $w$ is a valid committee for the entry
$D_{x}(C^{\prime},V^{\prime},k^{\prime})$ if all the following conditions hold
simultaneously:

  1. (1)

$w\subseteq C(T_{x})$;

  2. (2)

$C^{\prime}=C(B_{x})\cap w$; and

  3. (3)

a vote in $V(B_{x})$ has a representative in $w$ if and only if this vote is
in $V^{\prime}$, i.e., for every $v\in V(B_{x})$ it holds that $v\cap
w\neq\emptyset$ if and only if $v\in V^{\prime}$.

The value of the entry $D_{x}(C^{\prime},V^{\prime},k^{\prime})$ is the CCAV
score of an optimal valid $k^{\prime}$-committee for the entry. If
$D_{x}(C^{\prime},V^{\prime},k^{\prime})$ admits no valid
$k^{\prime}$-committees, we define
$D_{x}(C^{\prime},V^{\prime},k^{\prime})=-\infty$. Clearly, each table
associated with a bag has at most $2^{\omega+1}\cdot(k+1)$ entries.

The algorithm updates the tables from those associated with the leaves up to
the one associated with the root of $T$. The values of entries associated with
leaves are all $0$ (recall that each leaf bag is empty). We update the entry
$D_{x}(C^{\prime},V^{\prime},k^{\prime})$ associated with a nonleaf node $x$
in $T$ as follows.

First, if some candidate from $C^{\prime}$ is approved by some vote from
$V(B_{x})\setminus V^{\prime}$, we set
$D_{x}(C^{\prime},V^{\prime},k^{\prime})=-\infty$. Otherwise, we consider the
following cases with respect to the types of $x$.

  * •

$x$ is a join node

Let $y$ and $z$ be the two children of $x$. We have $B_{x}=B_{y}=B_{z}$. In
this case, we let

$D_{x}(C^{\prime},V^{\prime},k^{\prime})=\max_{\begin{subarray}{c}k^{\prime}_{1}+k^{\prime}_{2}=k^{\prime}-|C^{\prime}|\\\
0\leq k^{\prime}_{1}\leq|C(T_{y})\setminus C^{\prime}|\\\ 0\leq
k^{\prime}_{2}\leq|C(T_{z})\setminus C^{\prime}|\\\
V_{1}^{\prime},V_{2}^{\prime}\subseteq V^{\prime},V_{1}^{\prime}\cup
V_{2}^{\prime}=V^{\prime}\end{subarray}}\left\\{D_{y}\left(C^{\prime},V_{1}^{\prime},k^{\prime}_{1}+\left|C^{\prime}\right|\right)+D_{z}\left(C^{\prime},V_{2}^{\prime},k^{\prime}_{2}+\left|C^{\prime}\right|\right)-\left|V_{1}^{\prime}\cap
V_{2}^{\prime}\right|\right\\}.$

It is obvious that there are $O^{*}(2^{\omega})$ different combinations of
$k_{1}^{\prime}$, $k_{2}^{\prime}$, $V_{1}^{\prime}$, and $V_{2}^{\prime}$ to
consider in the max function. As a result,
$D_{x}(C^{\prime},V^{\prime},k^{\prime})$ can be computed in
$O^{*}(2^{\omega})$ time.

  * •

$x$ is an introduce node

Let $y$ be the child of $x$, and let $\\{h\\}=B_{x}\setminus B_{y}$. We
further distinguish between two subcases.

    * –

$h$ is a vote

If $h\not\in V^{\prime}$, then due to the above discussion $h$ does not
approve any candidates from $C^{\prime}$. We set
$D_{x}(C^{\prime},V^{\prime},k^{\prime})=D_{y}(C^{\prime},V^{\prime},k^{\prime})$.
If $h\in V^{\prime}$, then we set
$D_{x}(C^{\prime},V^{\prime},k^{\prime})=D_{y}(C^{\prime},V^{\prime}\setminus\\{h\\},k^{\prime})+1$
if $h$ approves at least one candidate from $C^{\prime}$; and set
$D_{x}(C^{\prime},V^{\prime},k^{\prime})=-\infty$ otherwise.

    * –

$h$ is a candidate

If $h\not\in C^{\prime}$, we set
$D_{x}(C^{\prime},V^{\prime},k^{\prime})=-\infty$ when
$k^{\prime}=|C(T_{x})|$, and set
$D_{x}(C^{\prime},V^{\prime},k^{\prime})=D_{y}(C^{\prime},V^{\prime},k^{\prime})$
when $k^{\prime}<|C(T_{x})|$.

If $h\in C^{\prime}$, let $V_{x}(h)$ be the submultiset of votes in
$V^{\prime}$ approving $h$. Then, we set

$D_{x}\left(C^{\prime},V^{\prime},k^{\prime}\right)=\max_{U\subseteq
V_{x}(h)}\left\\{D_{y}\left(C^{\prime}\setminus\left\\{h\right\\},V^{\prime}\setminus
U,k^{\prime}-1\right)+|U|\right\\}.$

Note that in this case if $V_{x}(h)=\emptyset$, we have that
$D_{x}(C^{\prime},V^{\prime},k^{\prime})=D_{y}(C^{\prime}\setminus\\{h\\},V^{\prime},k^{\prime}-1)$.
As $|V_{x}(h)|\leq\omega$, $D_{x}(C^{\prime},V^{\prime},k^{\prime})$ can be
calculated in $O^{*}(2^{\omega})$-time.

  * •

$x$ is a forget node

Let $y$ be the child of $x$ and let $\\{h\\}=B_{y}\setminus B_{x}$. We
consider the following two subcases.

    * –

$h$ is a vote

We set
$D_{x}\left(C^{\prime},V^{\prime},k^{\prime}\right)=\max\left\\{D_{y}\left(C^{\prime},V^{\prime},k^{\prime}\right),D_{y}\left(C^{\prime},V^{\prime}\cup\left\\{h\right\\},k^{\prime}\right)\right\\}$.

    * –

$h$ is a candidate

Clearly, $h\not\in C^{\prime}$. If $|C^{\prime}|=k^{\prime}$ or $h$ is
approved by some votes in $V(B_{x})\setminus V^{\prime}$, we set
$D_{x}(C^{\prime},V^{\prime},k^{\prime})=D_{y}(C^{\prime},V^{\prime},k^{\prime})$;
otherwise, let

$D_{x}\left(C^{\prime},V^{\prime},k^{\prime}\right)=\max\left\\{D_{y}\left(C^{\prime},V^{\prime},k^{\prime}\right),D_{y}\left(C^{\prime}\cup\left\\{h\right\\},V^{\prime},k^{\prime}\right)\right\\}.$

By the definition of the table, $D_{r}(\emptyset,\emptyset,k)$ is the CCAV
score of an optimal valid $k$-committee for the entry, where $r$ is the root
of $T$ (recall that the bag associated with the root is empty). By Conditions
(1)–(3) given above, every $k$-committee of $C$ is valid for
$D_{r}(\emptyset,\emptyset,k)$. Therefore, after all tables are computed, we
conclude that the given instance of CCAV-Multiwinner is a Yes-instance if and
only if $D_{r}(\emptyset,\emptyset,k)\geq d$.

It remains to analyze the running time of the algorithm. Each node in the nice
tree decomposition is associated with a table of $O^{*}(2^{\omega})$ entries.
Due to the above procedure, calculating an entry corresponding to a forget
node takes polynomial time, and calculating an entry corresponding to a join
or an introduce node takes $O^{*}(2^{\omega})$ time. As the nice tree
decomposition has polynomially many nodes, the running time of the algorithm
is $O^{*}(4^{\omega})$. ∎

Similar algorithms for PAV-Multiwinner and MAV-Multiwinner can be derived but
with the running time being bounded by $O^{*}({(k+1)^{\omega}})$. The reason
is that in these cases we need to maintain more information in order to solve
the problem. For example, for PAV-Multiwinner, we need to maintain for each
vote in $V^{\prime}$ the number of its approved candidates that are supposed
to be in a desired committee, which requests a table of size at least
$O^{*}((k+1)^{\omega})$.

######  Theorem 12.

PAV-Multiwinner and MAV-Multiwinner are _FPT_ with respect to the combined
parameter $k+\omega$, if a nice tree decomposition of width $\omega$ having
$\emph{{poly}}(p)$ nodes of the incidence graph of the input election is
given, where $p$ is the number of vertices of the incidence graph.

Proof To prove the theorem, we derive FPT-algorithms for PAV-Multiwinner and
MAV-Multiwinner with respect to $k+\omega$. Let $I=(E,k,d)$ be an instance of
$\tau$-Multiwinner where $\tau\in\\{\text{PAV},\text{MAV}\\}$, $E=(C,V)$, and
$k\leq|C|$. In addition, let $p=|C|+|V|$, and let $(T,\mathcal{B})$ be a nice
tree decomposition of $G_{E}$ of width $\omega$ that has $\textsf{poly}(p)$
nodes. The algorithms have the same skeleton as the one in the proof of
Theorem 11 for CCAV-Multiwinner. More concretely, we maintain a table for each
node of $T$, compute the tables in a bottom-up manner, and determine if the
given instance $I$ is a Yes-instance according to the table associated with
the root. To delineate the algorithms, we need the following notations. For an
integer $i$, we define $f(i)=\sum_{j=1}^{i}\frac{1}{j}$ if $i\geq 1$ and
define $f(i)=0$ otherwise. For a function $\varrho:A\rightarrow B$ and an
element $a\in A$, $\varrho_{-a}$ denotes $\varrho$ restricted to the domain
$A\setminus\\{a\\}$, i.e., $\varrho_{-a}:A\setminus\\{a\\}\rightarrow B$ is a
function such that for all $a^{\prime}\in A\setminus\\{a\\}$ it holds that
$\varrho_{-a}(a^{\prime})=\varrho(a^{\prime})$. Additionally, let $C(B_{x})$,
$V(B_{x})$, and $C(T_{x})$ be defined as in the proof of Theorem 11.
Furthermore, in parallel with $C(T_{x})$, we let $V(T_{x})$ denote the
multiset of all votes contained in bags associated with nodes in the subtree
rooted at $x$.

PAV. For each node $x$ in $T$, we maintain a table
$D_{x}(C^{\prime},k^{\prime},\mu)$ where $C^{\prime}\subseteq C(B_{x})$,
$|C^{\prime}|\leq k^{\prime}\leq\min\\{k,|C(T_{x})|\\}$, and
$\mu:V(B_{x})\rightarrow[k]\cup\\{0\\}$ is a function. We note that if
$V(B_{x})=\emptyset$, $\mu$ is an empty function. We say that a
$k^{\prime}$-committee $w\subseteq C(T_{x})$ is valid for
$D_{x}(C^{\prime},k^{\prime},\mu)$ if Conditions (1) and (2) listed in the
proof of Theorem 11, and the following condition are satisfied simultaneously:

  1. (4)

$|v\cap w|=\mu(v)$ for all $v\in V(B_{x})$.

We define $D_{x}(C^{\prime},k^{\prime},\mu)$ as the maximum possible PAV score
of $k^{\prime}$-committees valid for $D_{x}(C^{\prime},k^{\prime},\mu)$ with
respect to $V(T_{x})$. More precisely,

$D_{x}(C^{\prime},k^{\prime},\mu)\coloneqq\max_{\begin{subarray}{c}w\subseteq
C(T_{x}),|w|=k^{\prime}\\\ w~{}\text{is valid
for}~{}D_{x}(C^{\prime},k^{\prime},\mu)\end{subarray}}\textsf{PAV}(V(T_{x}),w),$

if $D_{x}(C^{\prime},k^{\prime},\mu)$ admits at least one valid
$k^{\prime}$-committee, and $D_{x}(C^{\prime},k^{\prime},\mu)=-\infty$
otherwise.

The tables for the leaves can be computed trivially according to the
definition of the tables. We show how to update an entry
$D_{x}(C^{\prime},k^{\prime},\mu)$ by distinguishing the types of the node
$x$.

  * •

$x$ is a join node

Let $y$ and $z$ be the two children of $x$. We let

$\begin{split}D_{x}(C^{\prime},k^{\prime},\mu)=\max_{k^{\prime}_{1},k^{\prime}_{2},\mu_{1},\mu_{2}}&\\{D_{y}\left(C^{\prime},k^{\prime}_{1}+\left|C^{\prime}\right|,{\mu_{1}^{\prime}}\right)-g(\mu_{1}^{\prime})\\\
&+D_{z}\left(C^{\prime},k^{\prime}_{2}+|C^{\prime}|,\mu_{2}^{\prime}\right)-g(\mu_{2}^{\prime})\\\
&+g(\mu)\\},\\\ \end{split}$

where

    1. (a)

$k^{\prime}_{1}$ and $k^{\prime}_{2}$ run over all integers so that
$k_{1}^{\prime}+k_{2}^{\prime}=k^{\prime}-|C^{\prime}|$, $0\leq
k^{\prime}_{1}\leq|C(T_{y})\setminus C^{\prime}|$, and $0\leq
k^{\prime}_{2}\leq|C(T_{z})\setminus C^{\prime}|$;

    2. (b)

$\mu_{1}$ and $\mu_{2}$ run over all functions from $V(B_{x})$ to nonnegative
integers so that for all $v\in V(B_{x})$ it holds that
$\mu_{1}(v)+\mu_{2}(v)=\mu(v)-|v\cap C^{\prime}|$;

    3. (c)

for each $i\in[2]$, $\mu_{i}^{\prime}$ is a function from ${V(B_{x})}$ to
$[k]\cup\\{0\\}$ so that $\mu_{i}^{\prime}(v)=\mu_{i}(v)+|v\cap C^{\prime}|$
for all $v\in V(B_{x})$; and

    4. (d)

for each $\rho\in\\{\mu,\mu_{1}^{\prime},\mu_{2}^{\prime}\\}$,
$g(\rho)=\sum_{v\in V(B_{x})}f(\rho(v))$.

By Condition (4), the number of different combinations of $\mu_{1}$ and
$\mu_{2}$ in (b) is bounded from above by $O^{*}((k+1)^{\omega+1})\cdot
O^{*}((k+1)^{\omega+1})=O^{*}(k^{2\omega})$. As a result, an entry in this
case can be computed in time $O^{*}(k^{2\omega})$. (Note that by the above
recursion, when $V(B_{x})=\emptyset$ we have that
$D_{x}(C^{\prime},k^{\prime},\mu)=\max_{k^{\prime}_{1},k^{\prime}_{2}}\\{D_{y}(C^{\prime},k^{\prime}_{1}+|C^{\prime}|,\mu)+D_{z}(C^{\prime},k^{\prime}_{2}+|C^{\prime}|,\mu)\\}$.)

  * •

$x$ is an introduce node

Let $y$ be the child of $x$, and let $\\{h\\}=B_{x}\setminus B_{y}$. We
further distinguish between the following two subcases.

    * –

$h$ is a vote

In this case, we set

$D_{x}(C^{\prime},k^{\prime},\mu)=\begin{cases}-\infty,&\text{if}~{}\mu(h)\neq|h\cap
C^{\prime}|\\\
D_{y}(C^{\prime},k^{\prime},\mu_{-h})+f(\mu(h)),&\text{otherwise}\\\
\end{cases}$

    * –

$h$ is a candidate

If $h\not\in C^{\prime}$, we set $D_{x}(C^{\prime},k^{\prime},\mu)=-\infty$
when $k^{\prime}=|C(T_{x})|$, and set
$D_{x}(C^{\prime},k^{\prime},\mu)=D_{y}(C^{\prime},k^{\prime},\mu)$ when
$k^{\prime}<|C(T_{x})|$.

If $h\in C^{\prime}$, we set $D_{x}(C^{\prime},k^{\prime},\mu)=-\infty$ if
there exists $v\in V(B_{x})$ such that $h\in v$ and $\mu(v)=0$, and set
$D_{x}(C^{\prime},k^{\prime},\mu)=D_{y}(C^{\prime}\setminus\\{h\\},k^{\prime}-1,\mu^{\prime})+\sum_{v\in
V(B_{x}),h\in v}\frac{1}{\mu(v)}$ otherwise, where
$\mu^{\prime}:V(B_{y})\rightarrow[k]\cup\\{0\\}$ is the function so that for
all $v\in V(B_{y})$ it holds that $\mu^{\prime}(v)=\mu(v)-|v\cap\\{h\\}|$. (If
$V(B_{x})=\emptyset$, $\mu^{\prime}$ is an empty function.)

  * •

$x$ is a forget node

Let $y$ be the child of $x$ and let $\\{h\\}=B_{y}\setminus B_{x}$. Similar to
the above case we distinguish between the following two subcases.

    * –

$h$ is a vote

We set
$D_{x}(C^{\prime},k^{\prime},\mu)=\max_{\begin{subarray}{c}\mu^{\prime}:V(B_{y})\rightarrow[k]\cup\\{0\\}\\\
\mu^{\prime}_{-h}=\mu\end{subarray}}D_{y}(C^{\prime},k^{\prime},\mu^{\prime})$.
Obviously, we have at most ${(k+1)^{\omega+1}}$ different functions
$\mu^{\prime}$ to check, and hence such an entry
$D_{x}(C^{\prime},k^{\prime},\mu)$ can be computed in $O^{*}({k}^{\omega})$
time.

    * –

$h$ is a candidate

In this case, we set

$D_{x}(C^{\prime},k^{\prime},\mu)=\begin{cases}D_{y}(C^{\prime},k^{\prime},\mu),&\text{if}~{}|C^{\prime}|=k^{\prime}\\\
\max\\{D_{y}(C^{\prime},k^{\prime},\mu),D_{y}(C^{\prime}\cup\\{h\\},k^{\prime},\mu)\\},&\text{otherwise}\\\
\end{cases}$

After the table for the root $r$ is computed, we conclude that the given
instance $I$ is a Yes-instance if and only if $D_{r}(\emptyset,k,\mu)\geq d$,
where $\mu$ is an empty function (recall that the bag associated with the root
is empty). This is because that by the definition of the table,
$D_{r}(\emptyset,k,\mu)$ is the maximum possible PAV score of a valid
$k$-committee for $D_{x}(\emptyset,k,\mu)$ with respect to $V(T_{r})=V$.

MAV. For each node $x$ in $T$, we maintain a table
$D_{x}(C^{\prime},k^{\prime},\mu)$ whose components are defined as with the
ones for PAV. The validity of a $k^{\prime}$-committee for an entry is also
defined the same. However, in this case each entry takes only binary values
$1$ and $0$. The entry $D_{x}(C^{\prime},k^{\prime},\mu)$ is $1$ if and only
if there is at least one $k^{\prime}$-committee $w$ which is valid for the
entry (i.e., a $k^{\prime}$-committee satisfying Conditions (1)–(2) in the
proof of Theorem 11, and Condition (4) given above) and, moreover, for each
$v\in V(T_{x})\setminus V(B_{x})$, it holds that $|w\cap
v|\geq\frac{k+|v|-d}{2}$. Observe that, by the definition of nice tree
decomposition, none of the votes in $V(T_{x})\setminus V(B_{x})$ approves any
candidates from $C\setminus C(T_{x})$. Therefore, for every $k$-committee
$w^{\prime}\subseteq C$ such that $w^{\prime}\cap C(T_{x})=w$ and every $v\in
V(T_{x})\setminus V(B_{x})$, it holds that $v\cap w=v\cap w^{\prime}$,
implying that the Hamming distance between $v$ and $w^{\prime}$ is at most $d$
if and only if $|v\cap w|\geq\frac{k+|v|-d}{2}$. The requirement $|w\cap
v|\geq\frac{k+|v|-d}{2}$ ensures that as long as the given instance admits a
Yes-witness $w^{\prime}\subseteq C$ such that $w^{\prime}\cap C(T_{x})=w$, the
existence of this Yes-witness is safely preserved in the table.

The tables for the leaves can be computed trivially according to their
definitions. We show how to update an entry $D_{x}(C^{\prime},k^{\prime},\mu)$
by distinguishing the types of the node $x$.

  * •

$x$ is a join node

Let $y$ and $z$ be the two children of $x$. In this case, we set
$D_{x}(C^{\prime},k^{\prime},\mu)=1$ if and only if there are two functions
$\mu_{1},\mu_{2}:V(B_{x})\rightarrow[k]\cup\\{0\\}$ and two nonnegative
integers $k_{1}^{\prime}$ and $k_{2}^{\prime}$ such that

    1. (a)

$k^{\prime}_{1}+k^{\prime}_{2}=k^{\prime}-|C^{\prime}|$;

    2. (b)

for all $v\in V(B_{x})$ it holds that $\mu_{1}(v)+\mu_{2}(v)=\mu(v)-|v\cap
C^{\prime}|$ and, moreover,

    3. (c)

$D_{y}\left(C^{\prime},k^{\prime}_{1}+|C^{\prime}|,{\mu_{1}^{\prime}}\right)=D_{z}\left(C^{\prime},k^{\prime}_{2}+|C^{\prime}|,\mu_{2}^{\prime}\right)=1$,
where for each $i\in[2]$, $\mu_{i}^{\prime}$ is the function from ${V(B_{x})}$
to $[k]\cup\\{0\\}$ so that $\mu_{i}^{\prime}(v)=\mu_{i}(v)+|v\cap
C^{\prime}|$ for all $v\in V(B_{x})$.

It is obvious that there are $O^{*}(k^{O(\omega)})$ different combinations of
$k_{1}^{\prime}$, $k_{2}^{\prime}$, $\mu_{1}$, and $\mu_{2}$ to enumerate. As
a result, it takes $O^{*}(k^{O(\omega)})$ time to compute
$D_{x}(C^{\prime},k^{\prime},\mu)$. (Note that when $V(B_{x})=\emptyset$, the
above recursion indicates that $D_{x}(C^{\prime},k^{\prime},\mu)=1$ if and
only if there are $k_{1}^{\prime}$ and $k_{2}^{\prime}$ as above so that
$D_{y}(C^{\prime},k_{1}^{\prime}+|C^{\prime}|,\mu)=D_{z}(C^{\prime},k_{2}^{\prime}+|C^{\prime}|,\mu)=1$.)

  * •

$x$ is an introduce node

Let $y$ be the child of $x$, and let $\\{h\\}=B_{x}\setminus B_{y}$. We
further distinguish between the following two subcases.

    * –

$h$ is a vote

We set $D_{x}(C^{\prime},k^{\prime},\mu)=1$ if and only if
$\mu(h)=|C^{\prime}\cap h|$ and $D_{y}(C^{\prime},k^{\prime},\mu_{-h})=1$.

    * –

$h$ is a candidate

If $h\not\in C^{\prime}$, we set $D_{x}(C^{\prime},k^{\prime},\mu)=0$ when
$k^{\prime}=|C(T_{x})|$, and set
$D_{x}(C^{\prime},k^{\prime},\mu)=D_{y}(C^{\prime},k^{\prime},\mu)$ when
$k^{\prime}<|C(T_{x})|$.

If $h\in C^{\prime}$, we set $D_{x}(C^{\prime},k^{\prime},\mu)=1$ if and only
if $D_{y}(C^{\prime}\setminus\\{h\\},k^{\prime}-1,\mu^{\prime})=1$ where
$\mu^{\prime}:V(B_{y})\rightarrow[k]\cup\\{0\\}$ is a function so that for all
$v\in V(B_{y})$ it holds that $\mu^{\prime}(v)=\mu(v)-|v\cap\\{h\\}|$. (When
$V(B_{x})=\emptyset$,
$D_{x}(C^{\prime},k^{\prime},\mu)=D_{y}(C^{\prime}\setminus\\{h\\},k^{\prime}-1,\mu)$.)

  * •

$x$ is a forget node

Let $y$ be the child of $x$ and let $\\{h\\}=B_{y}\setminus B_{x}$.

    * –

$h$ is a vote

We set $D_{x}(C^{\prime},k^{\prime},\mu)=1$ if and only if

      1. (1)

$\mu(h)\geq\frac{k+|h|-d}{2}$, and

      2. (2)

there is a function $\mu^{\prime}:V(B_{y})\rightarrow[k]\cup\\{0\\}$ so that
$\mu=\mu^{\prime}_{-h}$ and $D_{y}(C^{\prime},k^{\prime},\mu^{\prime})=1$.

The first condition is to ensure that there is a $k$-committee which contains
a valid $k^{\prime}$-committee $w$ for the entry and the Hamming distance
between $w$ and $h$ is at most $d$.

    * –

$h$ is a candidate

If $|C^{\prime}|=k^{\prime}$, we set
$D_{x}(C^{\prime},k^{\prime},\mu)=D_{y}(C^{\prime},k^{\prime},\mu)$.
Otherwise, we set $D_{x}(C^{\prime},k^{\prime},\mu)=1$ if and only if
$D_{y}(C^{\prime},k^{\prime},\mu)+D_{y}(C^{\prime}\cup\\{h\\},k^{\prime},\mu)\geq
1$.

After the table for the root $r$ is computed, we conclude that the given
instance $I$ is a Yes-instance if and only if $D_{r}(\emptyset,k,\mu)=1$,
where $\mu$ is an empty function. The reason for this is that by the
definition of the table, it holds that $D_{r}(\emptyset,k,\mu)=1$ if and only
if there is at least one $k$-committee $w\subseteq C(T_{r})=C$ which is valid
for $D_{r}(\emptyset,k,\mu)$ and, moreover, for each $v\in V(T_{r})\setminus
V(B_{r})=V$, it holds that $|w\cap v|\geq\frac{k+|v|-d}{2}$.

The running times of the algorithms for PAV-Multiwinner and MAV-Multiwinner
are dominated by the total size of all tables which is bounded from above by
$O^{*}(k^{O(\omega)})$. ∎

###  6.2 Maximum Matching

It is well-known that for every bipartite graph $G$, the size of a maximum
matching of $G$ equals the size of a minimum vertex cover of $G$ [55]. As the
treewidth of a graph is bounded from above by the size of a minimum vertex
cover of the graph [38], it follows from Theorem 11 that CCAV-Multiwinner is
FPT with respect to $\alpha(G_{E})$, where $E$ is a given election. We show
that MAV-Multiwinner and PAV-Multiwinner are also FPT with respect to this
parameter. Observe that the size of a maximum matching of $G_{E}$ can be at
most $\min\\{m,n\\}$, where $m$ is the number of candidates and $n$ is the
number of votes in the election $E$. Consequently, every FPT-algorithm with
respect to $\alpha(G_{E})$ also runs in FPT-time in $n$ and $m$.

######  Theorem 13.

MAV-Multiwinner and PAV-Multiwinner are _FPT_ with respect to $\alpha(G_{E})$,
where $E$ is the election in the input.

Proof Let $I=(E,k,d)$ be an instance of $\tau$-Multiwinner, where $E=(C,V)$
and $\tau\in\\{\text{MAV},\text{PAV}\\}$. Let $G_{E}$ be the incidence graph
of $E$, and let $M$ be a maximum matching of $G_{E}$. Hence,
$\alpha(G_{E})=|M|$. For simplicity, we write $\alpha$ for $\alpha(G_{E})$.
Let $C(M)$ and $V(M)$ be the set of candidates and the multiset of votes
saturated by $M$, respectively. Obviously, $|C(M)|=|V(M)|=\alpha$. We derive
algorithms for MAV and PAV as follows.

MAV. We split $I$ into at most $2^{\alpha}$ subinstances, each of which takes
$I$ and a subset $C^{\prime}\subseteq C(M)$ of size at most $k$ as input, and
asks whether there is a $k$-committee $w\subseteq C$ of MAV score at most $d$
such that $C^{\prime}=C(M)\cap w$. It is easy to see that $I$ is a Yes-
instance if and only if at least one of the subinstances is a Yes-instance. We
show how to solve each subinstance in polynomial time.

Let $I^{\prime}=(I,C^{\prime})$ be a subinstance. Let $v$ be a vote in
$V\setminus V(M)$. Assume that $w$ is a $k$-committee such that $w\cap
C(M)=C^{\prime}$. As $M$ is a maximum matching of $G_{E}$, no vote from
$V\setminus V(M)$ approves any candidate from $C\setminus C(M)$. Consequently,
the Hamming distance between $v$ and $w$ is $|v|+k-2|v\cap C^{\prime}|$.
Hence, if there is a vote in $V\setminus V(M)$ such that $|v|+k-2|v\cap
C^{\prime}|>d$, the subinstance is a No-instance. So, let us assume that this
is not the case. Now the task is to identify a subset $H$ of $k-|C^{\prime}|$
candidates from $C\setminus C(M)$ such that the Hamming distance between every
vote from $V(M)$ and the committee $H\cup C^{\prime}$ is at most $d$, or
equivalently, for every $v\in V(M)$, $H$ contains at least
$\frac{|v|+k-d}{2}-|v\cap C^{\prime}|$ of $v$’s approved candidates in
$C\setminus C(M)$. For each $v\in V(M)$, let $f(v)=\frac{|v|+k-d}{2}-|v\cap
C^{\prime}|$. We reduce the subinstance into an ILP with a bounded number of
variables. Specifically, for each $U\subseteq V(M)$, let $C_{U}$ be the set of
candidates in $C\setminus C(M)$ approved by all votes in $U$ but not approved
by any vote in $V(M)\setminus U$, and let $m_{U}=|C_{U}|$. For each
$U\subseteq V(M)$, we create one nonnegative integer variable $x_{U}$ which
indicates the number of candidates from $C_{U}$ that are supposed to be in a
desired committee. The constraints are as follows.

  * •

First, for each variable $x_{U}$ we have that $0\leq x_{U}\leq m_{U}$.

  * •

Second, as we seek $k-|C^{\prime}|$ candidates from $C\setminus C(M)$, it
holds that

$\sum_{U\subseteq V(M)}x_{U}=k-|C^{\prime}|.$

  * •

Finally, for every $v\in V(M)$, it holds that

$\sum_{U\subseteq V(M),v\in U}x_{U}\geq f(v).$

This inequality ensures that the Hamming distance between every vote $v\in
V(M)$ and the desired committee is at most $d$.

It is known that ILP is FPT with respect to the number of variables [52]. As
the above ILP has at most $2^{\alpha}$ variables, the subinstance can be
solved in FPT-time in $\alpha$. As there are at most $2^{\alpha}$
subinstances, the whole algorithm runs in FPT-time in $\alpha$.

PAV. The algorithm is analogous to the above one for MAV. First, we split the
given instance $I$ into subinstances by enumerating all possible intersections
$C^{\prime}$ of $C(M)$ and a desired $k$-committee. Then, every nonempty vote
$v\in V\setminus V(M)$ such that $v\cap C^{\prime}\neq\emptyset$ provides a
PAV score $\sum_{i=1}^{|v\cap C^{\prime}|}\frac{1}{i}$ to every $k$-committee
whose intersection with $C(M)$ is exactly $C^{\prime}$. Let

$d^{\prime}=\sum_{v\in V\setminus V(M),v\cap
C^{\prime}\neq\emptyset}\sum_{i=1}^{|v\cap C^{\prime}|}\frac{1}{i}.$

The question now is equivalent to solving an instance
$((C,V(M)),C^{\prime},k,d-d^{\prime})$ of Annotated PAV-Multiwinner, which can
be done in FPT-time in $|V(M)|=|M|=\alpha$ (Theorem 1). ∎

##  7 Conclusion

We have investigated the parameterized complexity of $\tau$-Multiwinner for
$\tau$ being the three prevalent approval-based $k$-committee selection rules
MAV, CCAV, and PAV, aiming at providing plentiful fixed-parameter tractability
results with respect to meaningful parameters. We studied many natural single
parameters, their combinations, and two structural parameters of incidence
graphs of elections, and obtained an almost complete landscape of the
parameterized complexity of $\tau$-Multiwinner for
$\tau\in\\{\text{MAV},\text{CCAV},\text{PAV}\\}$ with respect to these
parameters. For a summary of our concrete results, we refer to Table 1. It
should be noted that many of our tractability results were obtained by
reducing $\tau$-Multiwinner to well-studied graph/set problems. As advocated
by several researchers [31, 37], a remarkable advantage of using the reduction
scheme is that we can automatically update our results with the state-of-the-
art of these graph/set problems. In addition, though many reductions are
trivial and direct, we deem that pointing out the connections between
$\tau$-Multiwinner and the graph/set problems benefits researchers from
different communities.

Our exploration leaves several intriguing problems for future research. We
select two open questions that we believe to be the most challenging.

######  Open Question 1.

Is PAV-Multiwinner _FPT_ with respect to $d$?

######  Open Question 2.

Is PAV-Multiwinner _FPT_ with respect to the treewidth of the incidence graph
of the given election?

Besides these open questions, improving the FPT-algorithms presented in the
paper or investigating the kernelizations of FPT problems are also promising
avenues for future research. We remark that Agrawal et al. [2] studied
kernelizations of the Partial Hitting Set problem. Their results imply that
CCAV-Multiwinner admits a polynomial kernel with respect to
$d+\triangle_{\text{V}}$. It is interesting to see if the same holds for PAV-
Multiwinner. Regarding MAV, Misra, Nabeel, and Singh [58] have shown that MAV-
Multiwinner is unlikely to admit any polynomial kernels with respect to $d+m$
and $n+k$, assuming standard complexity hypothesis. This means that MAV-
Multiwinner is unlikely to admit any polynomial kernels with respect to
smaller parameters (e.g., $d$, $n$, $d+\triangle_{\text{V}}$, etc.).

Finally, we would like to mention that recently a few researchers have
examined a number of structural parameters based on real electoral data or
data generated by promising models, largely motivated by previous theoretical
works on the parameterized complexity of voting problems with respect to these
parameters (see, e.g., [11, 70]). Although graphs of small treewidth arisen
from various research areas have been continually reported in the literature,
to the best of our knowledge, analogous works on the treewidth of incidence
graphs of elections have not been conducted heretofore. We hope that our
algorithms presented in Section 6 would inspire such an investigation.

## Appendix

This appendix is devoted to the proof of Lemma 2. In the following, when we
remove a candidate from an election, we remove it from the candidate set and
from all votes approving the candidate.

Lemma 2. Let $\mathcal{H}$ be the set of all paths, cycles, hairsticks, and
DH-hairsticks. Then, given an $\mathcal{H}$-election, we can compute a PAV
optimal $k$-committee of the election in polynomial time.

Proof Let $E=(C,V)$ be an election whose multihypergraph representation $H(E)$
is either a path, a cycle, a hairstick, or a DH-hairstick. Let $k$ be a
nonnegative integer such that $k\leq|C|$. Let $n=|V|$. Note that $n$ is also
the number of vertices in $H(E)$. We consider all the possible cases of $H(E)$
as follows.

Case 1: $H(E)$ is a path or a cycle.

We first compute a maximum matching $M$ of $H(E)$. If $|M|\geq k$, it is easy
to see that the $k$-committee corresponding to $M$ is optimal. Otherwise, we
further distinguish between two subcases based on the parity of $n$. Let $w$
be the committee corresponding to $M$.

If $n$ is even, we know that $M$ is a perfect matching. Let $M^{\prime}$ be
the set of edges of $H(E)$ without $M$. Obviously, $M^{\prime}$ is also a
matching of $H(E)$. Let $C(M^{\prime})$ be the set of candidates corresponding
to $M^{\prime}$. As $M$ is a perfect matching, adding each $c\in
C(M^{\prime})$ into any committee containing $w$ and excluding $c$ increases
the PAV score of the committee by exactly one. In light of this fact, we add
any $k-|M|$ arbitrary candidates from $C(M^{\prime})$ into $w$, and return
$w$.

If $n$ is odd, there is exactly one vertex $v$ in $H(E)$ not saturated by $M$.
We put into $w$ one arbitrary candidate approved by $v$. Then, we arbitrarily
add $k-1-|M|$ candidates from the remaining candidates into $w$, and return
$w$.

Case 2: $H(E)$ is a hairstick.

If $k=n$, we return the whole set of candidates. Otherwise (i.e., $k<n$), a
key observation is that there exist optimal $k$-committees which do not
contain the candidate corresponding to the loop in $H(E)$. By this
observation, we directly remove the loop-candidate from the election. Now, the
election admits a path representation, and we use the algorithm described in
Case 1 to compute an optimal $k$-committee.

Case 3: $H(E)$ is a DH-hairstick.

If $k=n+1$, we return the whole set of candidates. Otherwise, there exist
optimal $k$-committees which contain at most one of the two candidates
corresponding to the loops in $H(E)$. In this case, we arbitrarily select one
loop, and remove the corresponding candidate from the election. Then, we
arrive at a hairstick representation of the election. The algorithm given in
Case 2 is applied to solve the problem.

It is easy to see that the above algorithms in all cases run in polynomial
time. ∎

## Acknowledgments

This work was supported in part by the National Natural Science Foundation of
China under Grant 62172446, and in part by the Open Project of Xiangjiang
Laboratory under Grants 22XJ02002 and 22XJ03005.

The authors would like to thank all anonymous reviewers who have provided
helpful comments on the paper.

## References

  * [1]
  * [2] Agrawal, A., Choudhary, P., Jain, P., Kanesh, L., Sahlot, V., Saurabh, S.: Hitting and covering partially.  In: COCOON, pp. 751–763 (2018)
  * [3] Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., Walsh, T.: Justified representation in approval-based committee voting.  Soc. Choice Welfare 48(2), 461–485 (2017)
  * [4] Aziz, H., Gaspers, S., Gudmundsson, J., Mackenzie, S., Mattei, N., Walsh, T.: Computational aspects of multi-winner approval voting.  In: AAMAS, pp. 107–115 (2015)
  * [5] Betzler, N., Slinko, A., Uhlmann, J.: On the computation of fully proportional representation.  J. Artif. Intell. Res. 47, 475–519 (2013)
  * [6] Bläser, M.: Computing small partial coverings.  Inf. Process. Lett. 85(6), 327–331 (2003)
  * [7] Bodlaender, H.L.: Fixed-parameter tractability of treewidth and pathwidth.  In: The Multivariate Algorithmic Revolution and Beyond, pp. 196–227 (2012)
  * [8] Bodlaender, H.L.: A tourist guide through treewidth.  Acta Cybern. 11(1-2), 1–21 (1993)
  * [9] Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $c^{k}n$ 5-approximation algorithm for treewidth.  SIAM J. Comput. 45(2), 317–378 (2016)
  * [10] Bodlaender, H.L., Kloks, T.: Better algorithms for the pathwidth and treewidth of graphs.  In: ICALP, pp. 544–555 (1991)
  * [11] Boehmer, N., Schaar, N.: Collecting, classifying, analyzing, and using real-world ranking data.  In: AAMAS. pp. 1706–1715 (2023)
  * [12] Brams, S.J., Kilgour, D.M., Sanver, M.R.: A minimax procedure for electing committees.  Public Choice 132(3-4), 401–420 (2007)
  * [13] Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey.  SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, USA (1999).
  * [14] Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Knop, D., Niedermeier, R.: Parameterized algorithms for finding a collective set of items.  In: AAAI. pp. 1838–1845 (2021)
  * [15] Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Niedermeier, R., Skowron, P., Talmon, N.: Robustness among multiwinner voting rules.  Artif. Intell. 290, Nr. 103403 (2021)
  * [16] Bredereck, R., Faliszewski, P., Niedermeier, R., Skowron, P., Talmon, N.: Mixed integer programming with convex/concave constraints: Fixed-parameter tractability and applications to multicovering and voting.  Theor. Comput. Sci. 814, 86–105 (2020)
  * [17] Byrka, J., Sornat, K.: PTAS for minimax approval voting.  In: WINE, pp. 203–217 (2014)
  * [18] Cai, L.: Parameterized complexity of cardinality constrained optimization problems.  Comput. J. 51(1), 102–121 (2008)
  * [19] Chamberlin, J.R., Courant, P.N.: Representative deliberations and representative decisions: Proportional representation and the Borda rule.  Am. Polit. Sci. Rev. 77(3), 718–733 (1983)
  * [20] Clearwater, A., Puppe, C., Slinko, A.: Generalizing the single-crossing property on lines and trees to intermediate preferences on median graphs.  In: IJCAI, pp. 32–38 (2015)
  * [21] Cornaz, D., Galand, L., Spanjaard, O.: Bounded single-peaked width and proportional representation.  In: ECAI, pp. 270–275 (2012)
  * [22] Courcelle, B., Mosbah, M: Monadic second-order evaluations on tree-decomposable graphs.  Theor. Comput. Sci. 109(1-2), 49–82 (1993)
  * [23] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms.  Springer (2015).
  * [24] Cygan, M., Kowalik, L., Socala, A., Sornat, K.: Approximation and parameterized complexity of minimax approval voting.  J. Artif. Intell. Res. 63, 495–513 (2018)
  * [25] Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs.  ACM Trans. Algorithms 11(2), Nr. 13 (2014)
  * [26] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer (2013)
  * [27] Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1].  Theor. Comput. Sci. 141(1-2), 109–131 (1995)
  * [28] Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness.  In: Complexity Theory: Current Research, pp. 191–225 (1992)
  * [29] Elkind, E., Faliszewski, P., Skowron, P., Slinko, A.: Properties of multiwinner voting rules.  Soc. Choice Welfare 48(3), 599–632 (2017)
  * [30] Elkind, E., Lackner, M.: Structure in dichotomous preferences.  In: IJCAI, pp. 2019–2025 (2015)
  * [31] Elkind, E., Lackner, M.: On detecting nearly structured preference profiles.  In: AAAI, pp. 661–667 (2014)
  * [32] Endriss, U. (eds.): Trends in Computational Social Choice.  AI Access (2017)
  * [33] Faliszewski, P., Skowron, P., Slinko, A., Talmon, N.: Multiwinner analogues of the plurality rule: Axiomatic and algorithmic perspectives.  Soc. Choice Welfare 51(3), 513–550 (2018)
  * [34] Faliszewski, P., Skowron, P., Slinko, A., Talmon, N.: Committee scoring rules: Axiomatic classification and hierarchy.  In: IJCAI, pp. 250–256 (2016)
  * [35] Faliszewski, P., Skowron, P., Talmon, N.: Bribery as a measure of candidate success: Complexity results for approval-based multiwinner rules.  In: AAMAS, pp. 6–14 (2017)
  * [36] Faliszewski, P., Slinko, A., Stahl, K., Talmon, N.: Achieving fully proportional representation by clustering voters.  J. Heuristics 24(5), 725–756 (2018)
  * [37] Fernau, H., Fomin, F.V., Lokshtanov, D., Mnich, M., Philip, G., Saurabh, S.: Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems.  Tsinghua Sci. Technol. 19(4), 374–386 (2014)
  * [38] Fomin, F.V., Liedloff, M., Montealegre, P., Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques.  Algorithmica 80(4), 1146–1169 (2018)
  * [39] Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems.  Theor. Comput. Sci. 1(3), 237–267 (1976)
  * [40] Gawron, G., Faliszewski. P.: Using multiwinner voting to search for movies.  In: EUMAS, pp. 134–151 (2022)
  * [41] Ghosh, S., Mundhe, M., Hernandez, K., Sen, S.: Voting for movies: The anatomy of a recommender system.  In: AGENTS, pp. 434–435 (1999)
  * [42] Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized vertex cover problems.  In: WADS, pp. 36–48 (2005)
  * [43] Gupta, S., Jain, P., Saurabh, S., Talmon, N.: Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules.  In: IJCAI, pp. 217–223 (2021)
  * [44] Kilgour, D.M.: Approval balloting for multi-winner elections.  In: Laslier, J.-F., Sanver, M.R. (eds.) Handbook on Approval Voting, pp. 105–124. Springer (2010).
  * [45] Kilgour, D.M., Marshall, E.: Approval balloting for fixed-size committees.  In: Felsenthal, D.S., Machover, M. (eds.) Electoral Systems—Paradoxes, Assumptions, and Procedures, pp. 305–326, Springer (2012).
  * [46] Kloks, T. (eds.): Treewidth: Computations and Approximations, _Lecture Notes in Computer Science_ , vol. 842.  Springer (1994).
  * [47] Kloks, T., Kratsch, D.: Treewidth of chordal bipartite graphs.  J. Algorithms 19(2), 266–281 (1995)
  * [48] Krause, P.K., Larisch, L., Salfelder, F.: The tree-width of C.  Discret. Appl. Math. 278, 136–152 (2020)
  * [49] Lackner, M., Skowron, P.: Multi-Winner Voting with Approval Preferences.  Springer (2023)
  * [50] Lackner, M., Skowron, P.: Consistent approval-based multi-winner rules.  J. Econ. Theory 192, Nr. 105173 (2021)
  * [51] LeGrand, R.: Analysis of the minimax procedure.  Techical Report, Department of Computer Science and Engineering, Washington University, St. Louis, USA (2004)
  * [52] Lenstra, H.W.: Integer programming with a fixed number of variables.  Math. Oper. Res. 8(4), 538–548 (1983)
  * [53] Lin, A.P.: The complexity of manipulating $k$-approval elections.  In: ICAART (2), pp. 212–218 (2011)  URL http://arxiv.org/abs/1005.4159
  * [54] Liu, H., Guo, J.: Parameterized complexity of winner determination in minimax committee elections.  In: AAMAS, pp. 341–349 (2016)
  * [55] Lovász, L., Plummer, M.D.: Matching Theory.  Elsevier, North Holland, Netherlands (1986)
  * [56] Maniu, S., Senellart, P., Jog, S.: An experimental study of the treewidth of real-world graph data.  In: ICDT, Nr. 12 (2019)
  * [57] Marchand, B., Ponty, Y., Bulteau, L.: Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics.  Algorithms Mol. Biol. 17(1), Nr. 8 (2022)
  * [58] Misra, N., Nabeel, A., Singh, H.: On the parameterized complexity of minimax approval voting.  In: AAMAS, pp. 97–105 (2015)
  * [59] Peters, D.: Single-peakedness and total unimodularity: New polynomial-time algorithms for multi-winner elections.  In: AAAI, pp. 1169–1176 (2018)
  * [60] Peters, D., Elkind, E.: Preferences single-peaked on nice trees.  In: AAAI, pp. 594–600 (2016)
  * [61] Peters, D., Lackner, M.: Preferences single-peaked on a circle.  J. Artif. Intell. Res. 68, 463–502 (2020)
  * [62] Procaccia, A.D., Rosenschein, J.S., Zohar, A.: On the complexity of achieving proportional representation.  Soc. Choice Welfare 30(3), 353–362 (2008)
  * [63] Procaccia, A.D., Rosenschein, J.S., Zohar, A.: Multi-winner elections: Complexity of manipulation, control and winner-determination.  In: IJCAI, pp. 1476–1481 (2007)
  * [64] Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width.  J. Algorithms 7(3), 309–322 (1986)
  * [65] Schrijver, A.: Theory of Linear and Integer Programming.  John Wiley & Sons, Inc., New York, USA (1986)
  * [66] Skowron, P.: FPT approximation schemes for maximizing submodular functions.  Inf. Comput. 257, 65–78 (2017)
  * [67] Skowron, P., Faliszewski, P.: Chamberlin-Courant rule with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time.  J. Artif. Intell. Res. 60, 687–716 (2017)
  * [68] Skowron, P., Faliszewski, P., Lang, J.: Finding a collective set of items: From proportional multirepresentation to group recommendation.  Artif. Intell. 241, 191–216 (2016)
  * [69] Skowron, P., Yu, L., Faliszewski, P., Elkind, E.: The complexity of fully proportional representation for single-crossing electorates.  Theor. Comput. Sci. 569, 43–57 (2015)
  * [70] Sui, X., Francois-Nienaber, A., Boutilier, C.: Multi-dimensional single-peaked consistency and its approximations.  In: IJCAI, pp. 375–382 (2013)
  * [71] Thiele, T.N.: Om Flerfoldsvalg.  In: Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, pp. 415–441 (1895)
  * [72] Thorup, M.: All structured programs have small tree-width and good register allocation.  Inf. Comput. 142(2), 159–181 (1998)
  * [73] van der Zanden, T.C.: Theory and practical applications of treewidth.  Ph.D. thesis, Utrecht University, Netherlands (2019).
  * [74] West, D.B.: Introduction to Graph Theory.  Prentice-Hall (2000)
  * [75] Yamaguchi, A., Aoki, K.F., Mamitsuka, H.: Graph complexity of chemical compounds in biological pathways.  Genome Informatics 14, 376–377 (2003)
  * [76] Yang, Y.: A model of winners allocation.  In: AAAI, pp. 5760–5767 (2021)
  * [77] Yang, Y.: On the complexity of destructive bribery in approval-based multi-winner voting.  In: AAMAS, pp. 1584–1592 (2020)
  * [78] Yang, Y.: Complexity of manipulating and controlling approval-based multiwinner voting.  In: IJCAI, pp. 637–643 (2019)
  * [79] Yang, Y.: On the tree representations of dichotomous preferences.  In: IJCAI, pp. 644–650 (2019)
  * [80] Yang, Y., Guo, J.: The control complexity of $r$-approval: From the single-peaked case to the general case.  J. Comput. Syst. Sci. 89, 432–449 (2017)
  * [81] Yang, Y., Wang, J.: Parameterized complexity of multi-winner determination: More effort towards fixed-parameter tractability.  In: AAMAS, pp. 2142–2144 (2018)
  * [82] Yu, L., Chan, H., Elkind, E.: Multiwinner elections under preferences that are single-peaked on a tree.  In: IJCAI, pp. 425–431 (2013)