More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules

1 Introduction

MULTIWINNER ELECTION is one of the well-studied problems in computational social choice theory [Ballotpedia, 2024; Faliszewski et al., 2017; Elkind et al., 2017; Pierczynski and Skowron, 2019]; and the most extensively studied and commonly implemented in practice is the approvalbased model of election [Skowron and Faliszewski, 2015; Skowron and Faliszewski, 2017; Skowron, 2017; Lackner and Skowron, 2021; Lackner and Skowron, 2023; Do et al., 2022]. In general, a multi-winner election with approval preferences consists of a set of m candidates (C), a set of n voters

(V), each providing a set of approved candidates Av ⊆ C, a satisfaction (or scoring) function sco : 2C → Q≥0, and an integer k. The set of approval list of all voters is called the approval profile denoted by A = {Av : v ∈ V}. The goal here is to select a subset (called a committee) S of k candidates that maximizes the value sco(S). In the decision version the goal is to check if sco(S) ≥ t for a given value t. The definition of the sco(·) function depends on the voting rule we employ. In this article, we consider a subclass of approval-based voting rules (known as the ABC voting rules). An important class of ABC rules is the one defined by Thiele [Lackner and Skowron, 2023] (also known as generalised approval procedures). Some of the well-known Thiele rules are approval voting, Chamberlin-Courant, and proportional approval voting(PAV) [Chamberlin and Courant, 1983; Janson, 2016]. A Thiele rule is given by a function f : N ∪ {0} → Q≥0 where f(0) = 0. For example, under the Chamberlin-Courant rule, f(i) = 1 for each i > 0, while for the Proportional Approval Voting (PAV) rule, f (i) = ∑ij=1 1j for each i > 0. Given a profile A, the score of a committee S ⊆ C is defined by sco(S) = ∑v∈V f(|S ∩ Av|). Since our paper deals with different functions, as well as different approval profiles, for the sake of clarity, we denote the score function as scof(A, S) = ∑v∈V f(|S ∩ Av|). We leave f and A from the notation if it is clear from the context.

Context of Our Results. In general, the MULTIWINNER ELECTION problem, aka the COMMITTEE SELECTION problem, is NP-hard. In fact, the problem is also intractable in the realm of parameterized complexity, W[2]-hard with respect to k, the size of the committee. That is, we do not expect an algorithm with running time h(k)(n + m)O(1) . In fact, these intractability results carry over even for special cases. In particular, given a Thiele function f : N ∪ {0} → Q+, for each voter v ∈ V, we can associate a satisfaction function with each committee, defined as fv : 2C → Q+ where fv(S) = f(|S ∩ Av|). In this notation, the score of S is given by scof(A, S) = ∑v∈V fv(S). When the function fv is monotone and submodular, for each voter v ∈ V , we call the problem SUBMODULAR MULTIWINNER ELECTION (SM-MWE). It is known that SM-MWE is NP-hard as well as W[2]-hard with respect to parameter k [Aziz et al., 2015; Yang and Wang, 2023]. Aziz et el. [2015] shows that the problem under PAV rule remains W[2]-hard even for the special case where each voter approves at most two candidates. A similar hardness for the Chamberlin-Courant rule was shown by [Yang and Wang, 2023]. They also show that the problem for both Chamberlin-Courant rule and PAV remains W[1]-hard when parameterized by (|C| - k) = m - k even when every voter approves two candidates. They also show that under Chamberlin-Courant rule the problem admits an FPT algorithm parameterized by t, i.e., the threshold value in the decision version of the problem. However, they state that the FPT membership of the problem under the PAV rule with respect to t as an open question. We answer this by providing an FPT algorithm parameterized by t, k for SM-MWE and parameterized by t under the PAV rule. We use color coding techniques introduced by [Alon et al., 1995].(Detailed proof in full version)

In the world of approximation algorithms, due to [Manurangsi, 2020] we know that we cannot hope to find a k-sized committee with score at least (1 - 1e - ϵ)OPT even in time f(k)(|C| + |V|)o(k) . Here, OPT denotes the maximum score of a committee of size k. To mitigate these intractability results Skowron [2017] considers special cases of this problem. In particular, he looks at the case where the approval list is bounded by an integer δ, that is, every voter approves at most δ candidates. It was already known that even for δ = 2, SM-MWE is NP-hard and W[1]-hard [Aziz et al., 2015; Betzler et al., 2013]. This led Skowron to consider the existence of parameterized approximation that is, an approximation algorithm that runs in time h(k, δ)(n +m)O(1) where h is any computable function. In particular, he observed that the problem admits a (1- 1e )-factor approximation in polynomial time. In addition, for each ϵ > 0, he presented, an approximation scheme that runs in time h(k, d, ϵ)(n +m)O(1) and produces a k-sized subset S such that scof (A, S) ≥ (1-ϵ)OPT. We call such an approximation scheme an FPT-AS and is the starting point of this work.

It is known that even when ∆C = 3 (maximum number of voters approving the same candidate) and δ = 2 (maximum number of candidates approved by the same voter) SM-MWE is NP-hard [Procaccia et al., 2007; Aziz et al., 2015]. We show that SM-MWE is FPT when parameterised by k +∆C (Proof can be found in the full version).

Our Results and Overview. For our study of parameterized approximation algorithms, we consider a parameter d smaller than δ as well as ∆C. Here, d denotes the smallest number such that that no d voters approve the same set of d candidates. Clearly, d ≤ δ as well as d ≤ ∆C. Since it is a smaller parameter, it is worth considering. There are realistic scenarios where d is indeed much smaller than δ and ∆C. Consider a university election of a 10-member committee from 200 candidates, with 5,000 students voting, where the votes are presumably based on personal connections and shared interests. The large diverse student body makes it unlikely for any d students to approve the same d candidates, thereby resulting in unique voting patterns.

For the ease of exposition, we consider the profile graph of approval-based elections. It is a bipartite graph G = (C, V, E), where V (G) = C ⊎ V, and E is the edge set. Note that C is the set of candidates, V is the set of voters. For a candidate c ∈ C and a voter v ∈ V, we add an edge cv if the voter v approves the candidate c, i.e c ∈ Av. In profile graph the approval list of voter v,Av is the set {c ∈ C : vc ∈ E(G)}. Given a graph G and a function fv for every v ∈ V, the objective function is same as above, i.e., find a subset S ⊆ C of size k that maximises scof (G, S) = ∑v∈V fv(|S ∩ Av|). The graph G is Kd,d-free (i.e., it does not contain a complete bipartite graph with d vertices on each side as an induced subgraph).

Jain et al. [2023] consider the MAXIMUM COVERAGE problem (which is equivalent to Chamberlin-Courant based MWE) and give an FPT-AS with respect to the parameter k + d when the profile graph is Kd,d-free. Manurangasi [2025] designed a polynomial-time lossy kernel for the same problem.

Similar to the results of Jain et al. [2023] for MAXIMUM COVERAGE we obtain the following set of results for SMMWE, when profile graph of the given instance is Kd,d-free. In the following a solution refers to a k-sized committee.

• We present an FPT-AS parameterized by k. That is we give an algorithm that given 0 < ϵ < 1, runs in time ( dk ϵ )O(d2 k) (n +m)O(1) , and outputs a solution whose score is at least (1 - ϵ) fraction of the optimum, Theorem 1.
• We complement FPT-AS, by designing a polynomial time lossy kernel with respect to k for SM-MWE. (Observe that a normal "lossless" kernel is not possible with respect to k, since the problem is W[1]-hard, and thus no FPT algorithm and equivalently a kernel, may exist.) In other words, we present a polynomial-time algorithm that produces a graph G′ of size polynomial in k + ϵ from which we can find a solution that attains a (1 - ϵ) fraction of the optimal score in the original instance, Theorem 2. Observe that in most practical scenarios, k is some fixed small constant and thus searching for the desired committee in the reduced instance is quite efficient. Moreover, we also note that G′ represents the reality that only a small subset of voters and candidates actually matter!

The starting point of our lossy kernel is the result of [Manurangsi, 2024]. In particular, the kernelization algorithm involves the following steps: it assesses the potential value of the score, and if this value is upper-bounded by a polynomial function of k and ϵ, we can then construct a lossless kernel. Else, we first define a notion that leads to a reduction rule for identifying candidates who are similar in terms of approximating the optimal score. Exhaustive application allows us to reduce the size of the candidate set to a polynomial function of k and ϵ. Finally, by applying another reduction rule that identifies distinct approval lists, we can reduce the number of voters, resulting in the desired lossy kernel.

• We also present an FPT approximation algorithm parameterized by k, d that outputs a k+1-sized committee whose score is the same as the optimal solution of size k, Theorem 3.

In fact, our algorithm works even when we have different Thiele functions hv for each voter v. Then the associated satisfaction function fv : 2C → Q+ can be represented as fv(S) = hv(|S ∩ Av|). This strictly generalizes the known model as for each v, hv is the same. Our results build on existing algorithms for MAX COVERAGE and MAXIMIZING SUBMODULAR FUNCTIONS. However, due to the inherent generality of our problems, both in terms of the scoring function and the class of profiles, we must deviate significantly from known approaches in several crucial and key aspects.

2 Our Problem in OWA Framework

We will reformulate our problem within the Ordered Weighted Average (OWA) framework to align with existing results in the literature. We refer to Section 4.1 in the article of Skowron [Skowron, 2017] for further details. Given a set of candidates C, a set of voters V and the approval list Av of every voter v ∈ V, and a Thiele rule given by a non-decreasing function f : N ∪ {0} → Q+ with f(0) = 0, we define an OWA vector λ as follows. For every i ≥ 1, λi = f(i) - f(i - 1). Then, we have f(|S ∩ Av|) = ∑|S∩Av | j=1 λj. Thus, the scoring function can also be expressed as scoG(S) = ∑v∈V ∑|S∩Av| j=1 λj. Hence, every Thiele rule like CC, PAV can be expressed by an OWA vector. Now, we make the following claim.

Lemma 1. (♣)1 The functions fv, v ∈ V, is monotone and submodular if and only if the corresponding OWA vector λ is non-increasing. Here, fv is the satisfaction function corresponding to the voter v derived from f.

We design our algorithms for the scenario where each voter has their own Thiele function 2 . Thus, instead of a single OWA vector, we work with a family Λ = {λv | v ∈ V} of OWA vectors. Throughout this paper, we assume that for any given non-increasing OWA vector λv = (λv1 , λv2 , . . . , λv|Av| ) we have λv1 ≤ 1 for any v ∈ V. Suppose not, then we can divide every λvi by λmax = max{λv1 | v ∈ V} and change t to t λmax where t corresponds to total score and is described in problem definition below. Given a bipartite graph G = (C, V,E) and a set Λ of OWA vectors, λv , for every v ∈ V, we define a restriction operation ΛS for every S ⊆ C.

Definition 2. For any j ∈ [|Av|], we use λv-j to denote the (shortened) OWA vector obtained by deleting the j-sized prefix of λv . That is, λv-j = (λvj+1 , λvj+2 , . . . , λv|Av| ).

For the set of OWA vectors Λ and a subset of candidates S ⊆ C, we defineΛS = {λv-j : v ∈ V and j = |N(v)3∩S|}. In other words, ΛS is obtained by removing the |N(v) ∩ S|- sized prefix from λv , if v ∈ N(S); else we retain λv intact.

Let λmin denote min{λv1 | v ∈ V}

1 Proofs of results marked with (♣)can be found in the full version at http://arxiv.org/abs/2505.12699.

2 Note that we are presenting algorithms for the general model, however, this is the first work even when the Thiele function is the same for every voter.

3N(·) denotes the neighborhood

Algorithm 1 Apx-MwE: An FPT-approximation scheme for SM-MWE

Input: A bipartite graph G = (C, V, E), a set Λ = {λv : v ∈ V}, integers k, t, and ϵ > 0

Output: A k-sized subset S ⊆ C such that scoG(S) ≥ (1 - ϵ)t.

• 2: Apply Reduction Rule 1 exhaustively to get G′ = (C ′ , V).
• 3: Search all k-sized subsets of C ′ . Let S ⊆ C ′ that achieves the maximum sco.
• 4: if scoG(S) ≥ t then return S.
• 5: else return no-instance.
• 6: if t > 2krd (d-1) (r-k)ϵ then
• 7: Let Cr denote the ⌈r⌉ vertices of C with the highest sco(·)-value.
• 8: Let S denote the k-sized subset of Cr with maximum scoG(·) value.
• 9: if scoG(S) ≥ (1 - ϵ)t then return S.
• 10: else return no-instance.

When Λ, G are clear from the context, we will use sco(S) or scoG(S) instead of scoΛG(S). For a set O and a singleton set {x} we sometimes omit the braces during set operations. For example, O\{x} and O\x represent the same set.

3 FPT-AS for SM-MWE

For clarity, we state the problem here.

SM-MWE

Parameter: k

Input: A bipartite graph G = (C, V,E), a set Λ of non-increasing vectors λv = (λv1 , λv2 , . . . , λv|Av| ) for all v ∈ V, and positive integers k and t.

Question: Does there exist S ⊆ C such that |S| ≤ k and scoΛG(S) = ∑v∈V fG,v(S) ≥ t where fG,v(S) = ∑|NG(v)∩S| j=1 λvj ?

Overview of the algorithm. We derive our algorithm by considering two cases: "low" threshold (value of t) and "high" threshold. For "low" threshold, we use a sunflower lemma-based reduction rule to reduce candidates. For "high" threshold, we discard all but a sufficiently large number of candidates with the highest sco(·) value. The formal description is presented in Algorithm 1.

Next, we will define a sunflower that is used in our proof. In a bipartite graph G(C, V,E), a subset S ⊆ C is said to form a sunflower if NG(x)∩NG(x′ ) (i.e the "approving set") are the same for all distinct candidates x, x′ ∈ S. For a given sunflower S, we will refer to the common intersection of the neighborhood, ∩x∈SN(x) as Co(S).

Proposition 3. [Manurangsi, 2024][Ka,b-free sunflower] For any w, l ∈ N, let G((C, V),E) be a Ka,b-free bipartite graph such that every vertex in C has degree at most ℓ

and |C| ≥ a((w - 1)ℓ)b . Then, G has a sunflower of size w. Moreover, a sunflower can be found in polynomial time.

Theorem 1. There exists an algorithm running in time ( dk ϵ )O(d2 k)nO(1) that given an instance of SM-MWE, where the input graph is Kd,d-free, outputs a solution S such that scoΛG(S) ≥ (1 - ϵ)t.

Proof. We will design and run two different algorithms for two possible cases, based on the value of t (we call it threshold). A brief description of FPT-AS that combines both cases is given in Algorithm 1. Recall that we defined λmin = min{λv1 | v ∈ V}. Let r = 4dk ϵλmin + k.

Analysis of Case 1. In this case, we will apply a modified sunflower lemma to reduce the number of candidates and then find an optimal solution using exhaustive search. Thus, for this case, we solve the problem optimally.

We begin by observing that if there exists a vertex v ∈ C with deg(v) ≥ 2krd (d-1) (r-k)ϵλmin , then {v} itself is a solution since t ≤ 2krd (d-1) (r-k)ϵλmin λmin. This is because each of the neighbors of v contribute at least λmin to scoG({v}). Hence, scoG({v}) ≥ 2krd (d-1) (r-k)ϵλmin λmin ≥ t. Thus, we may assume that for each v ∈ C, deg(v) < 2krd (d-1) (r-k)ϵλmin .

Let W = 2krd (d-1) (r-k)ϵλmin , the maximum degree of a vertex in C. We apply the following reduction rule to the instance I = (G = (C, V, E), k, t, Λ) exhaustively.

Reduction Rule 1. Use Proposition 3 on G, where a = b = d and ℓ = W. If a sunflower of size at least w = Wk + 1 is found, then delete the vertex (candidate), say u, with the lowest scoΛG({u}) value in the sunflower (ties are broken arbitrarily). Return instance I ′ = (G′ = (C\{u}, V), k, t, Λ).

Lemma 4 proves the correctness of our reduction rule.

Lemma 4. I is a yes-instance iff I ′ is a yes-instance.

Proof. If I ′ is a yes-instance, then clearly I is a yes-instance as well because for any solution S in I ′ we have scoG(S) = scoG′ (S).

Next, for the other direction suppose that I = (G, k, t, Λ) is a yes-instance. Let S denote a solution to I. Let u denote the vertex in the sunflower T that is deleted by the reduction rule. If u ∈ C \S, then S is a solution in I ′ .

Suppose that u ∈ S. We will show that there is another candidate that can replace u to yield a solution in I ′ . Formally, we argue as follows. Since |S| ≤ k, we have |N(S)| ≤ Wk. For each candidate x ∈ T, we call the set N(x) \Co(T) the petal of x. Since |T | = Wk + 1, there are Wk + 1 petals in V. The voters in N(S) can be present in at most Wk petals. Thus, there is at least one petal, corresponding to some candidate v ∈ T , that does not contain any vertex in N(S). That is, (N(v) \Co(T)) ∩N(S) = ∅. Using this candidate v, we define the set S′ = S ∪ {v} \{u}. We will next prove that scoG′(S′ ) ≥ scoG(S). Consequently, it follows that S′ is a solution in I ′ .

We begin the argument by noting that the petal of v, N(v) \Co(T) ⊆ N(T) \N(S) and the contribution of the voters in the petal to S′ is ∑x∈N(v)\Co(T) λx1 . The score of S′ consists of the score given by voters in V \(N(u) ∪N(v)) whose contribution is unchanged between S and S′ , as are the contributions of the voters in Co(T). The voters who experience a change are in N(u) \Co(T) who have one fewer representative in S′ , and those in N(v) \Co(T), who contribute ∑x∈N(v)\Co(T) λx1 . Following claim completes the proof.

Hence, the lemma is proved.

Exhaustive application of Reduction Rule 1 yields an instance I ′ in which a sunflower of size Wk+1 does not exist. Then, according to Proposition 3, |C ′ | < d(W 2k)d where a = b = d, ℓ = W and w = Wk + 1.

Notice that Reduction Rule 1 can be implemented in time polynomial in |I|, and the number of times it can be applied is also polynomial in |I|. Hence, the running time in this case is (|C′ | k )nO(1) = ( dk ϵ )O(d2 k) nO(1) . This completes the analysis for Case 1. Next, we will analyze Case 2.

Analysis of Case 2. We prove the existence of an approximate solution by showing that starting from an optimal solution, we can create our solution Oℓ in a step-by-step fashion. Claim 3 allows us to bound for the ith step, the number of voters a top r-candidate may share with the candidates in Oi. This in turn implies that we can replace candidate xi by someone in Cr \Oi without too much loss in score. Claim 4 allows us to give a counting argument that yields that the difference sco(O) - sco(Oℓ) = ∑ℓi=1 αi ≤ ϵ · sco(O). Let O denote a solution for an instance I of SM-MWE, i.e., sco(O) ≥ t. Recall that Cr is defined to be the set of ⌈r⌉ candidates in C with the highest sco (·) value. If O ⊆ Cr, then the exhaustive search of Line 8 will yield the solution O. Therefore, without loss of generality, we may assume that O \Cr ̸= ∅. Let O\Cr = {x1, . . . , xℓ}, where ℓ ∈ [k]. We define O1 = (O\{x1}) ∪ {y1} where y1 ∈ Cr\O such that y1 minimizes the value sco(O)-sco(O1). Similarly, for any i ∈ [ℓ], we define Oi = (Oi-1 \{xi}) ∪ {yi} where yi ∈ Cr \Oi-1 such that sco(Oi-1) - sco(Oi) is minimum. For each i ∈ [ℓ - 1], we define αi = sco(Oi) - sco(Oi+1).

Claim 3. (♣)Let p be any candidate in Cr \Oi. Then, for any i ∈ [ℓ], we have |N(Oi) ∩ N(p)| ≥ αi-1.

Now consider the graph G induced on Cr\Oℓ and N(O ∪ Oℓ). The number of edges incident on Cr\Oℓ is at least (|Cr| - k)αi because for every p ∈ Cr\Oℓ, we have |N(O ∪ Oℓ)∩N(p)| ≥ αi due to Claim 3. The number of edges incident on N(O∪Oℓ) is at most 2d·sco(O)/λmin+|Cr|d (d-1), Claim 4. This is because vertices with degrees at most d can contribute 2d · sco(O)/λmin. Since the input graph is Kd,d-free, the remaining vertices can contribute at most (|Cr | d )(d-1) to the total number of incident edges. Using this inequality we prove the following claim.

Thus, we have shown that there exists Oℓ ⊆ Cr that is a (1 - ϵ)-approximate solution which proves the correctness of our algorithm. Moreover, we get the following result.

Claim 6. If t > 2krd (d-1) (r-k)ϵ , where r = 4dk ϵλmin + k, then the set of ⌈r⌉ vertices in C with highest sco(·) contains a solution with sco(·) at least (1 - ϵ)t.

The running time in this case is atmost (⌈r⌉ k )nO(1) = (dk/ϵ)O(k)nO(1) . Thus, we have the desired FPT-AS.

4 Lossy Kernel for SM-MWE

In this section, we give a kernel for our problem when the profile graph is Kd,d-free. Towards this, we first define the optimization version of SM-MWE below.

MAX SUBMOD-MWE Parameter: k Input: A bipartite graph G = (C, V), an integer k, and a set Λ of non-increasing vectors λv = (λv1 , λv2 , . . . , λv|Av| ) for every v ∈ V.

Question: Find S ⊆ C such that |S| ≤ k and scoΛG(S) = ∑v∈V fG,v(S) is maximized, where

Here C represents the set of candidates and V represents the set of voters. For v ∈ V, the set N(v) represents the approval list Av of voter v. Let ˆ S ⊆ C and | ˆ S| ≤ k such that scoΛG( ˆ S) is maximum. Then, OPTG,k,Λ = scoΛG( ˆ S). We also assume without loss of generality that all the voters have a nonzero OWA vector. Otherwise, if the vector corresponding to a voter is (0, 0, . . . 0), we can safely delete the vertex corresponding to that voter. By Iden, we denote an algorithm that outputs the input itself. We next describe some terminology.

Definition 5. [Lokshtanov et al., 2017][α-APPA] Let α, β ∈ (0, 1). An α-approximate polynomial-time pre-processing algorithm (α-APPA) for a parameterized optimization problem Π is a pair of polynomial-time algorithms A and B called the reduction algorithm and solution lifting algorithm respectively such that the following holds:

1. given any instance (I, k) of Π, A outputs an instance (I ′ , k′ ) of Π, and
2. given any β-approximate solution of (I ′ , k′ ), B outputs an αβ-approximate solution of (I, k).

Definition 6. [Lokshtanov et al., 2017][α-approximate kernel] Let α ∈ (0, 1). An α-approximate kernel is an α-APPA such that the output size |I ′ | + k′ is bounded by some computable function of k.

Definition 7. [Manurangsi, 2024][(α, γ)-APPA ] Let α, γ ∈ (0, 1). An (α, γ)-approximate polynomial-time preprocessing algorithm((α, γ)-APPA) for a parameterized optimization problem Π is a pair of polynomial-time algorithms A and B called the reduction algorithm and solution lifting algorithm respectively such that the following holds:

1. given any instance (I, k) of Π, A outputs an instance (I ′ , k′ ) of Π, and
2. given any β-approximate solution of (I ′ , k′ ), B outputs an (αβ - γ)-approximate solution of (I, k).

Proposition 8. [Manurangsi, 2024] For any ϵ1, ϵ2, c ∈ (0, 1), suppose that a maximization problem admits a polynomialtime c-approximation algorithm and a (1 - ϵ1, ϵ2)-APPA. Then, it admits a (1 - ϵ1 - ϵ2/c)-APPA with the same reduction algorithm.

Due to [Nemhauser et al., 1978], we know that the greedy algorithm for maximizing submodular functions is a (1- 1e )- approximate algorithm. The satisfaction function fG,v(·) of each voter, v, is a non-decreasing submodular function [Skowron and Faliszewski, 2015]. Since the sum of submodular functions is also submodular, we have the following.

Lemma 9. There is a polynomial-time (1- 1e )-approximation algorithm for MAX SUBMOD-MWE.

We will split the kernel construction into two parts: first we will describe the analysis that allows us to reduce the number of candidates followed by the analysis that allows us to reduce the number of voters.

Reducing the Number of Candidates

Lemma 10. (♣) Suppose that A is a parameter-preserving reduction algorithm for MAX SUBMOD-MWE that on input I = (G, k,Λ) just deletes a subset of candidates resulting in the instance I ′ = (G′ , k,Λ). If OPTG′ ,k,Λ ≥ (1 - δ) · OPTG,k,Λ for some δ ∈ (0, 1), then (A, Iden) is a (1 - δ)- APPA.

Lemma 11. For any ϵ ∈ (0, 1), there is a parameterpreserving (1-ϵ)-APPA for MAX SUBMOD-MWE when the profile graph is Kd,d-free, such that the output has ( dk ϵ )O(d2 ) candidates.

Proof. We apply the polynomial time (1- 1e )-approximation algorithm from Lemma 9. Let ApxOPT denote the sco of the returned solution and r = 4dk ϵλmin + k. We have the following two cases:

Case 1: ApxOPT > 2krd (d-1) (r-k)ϵ . In this case, we delete all but the r highest degree vertices in C. We will show that OPTG′ ,k,Λ ≥ (1 - ϵ)OPTG,k,Λ, then, by Lemma 10 it follows that we have a (1 - ϵ)-APPA. We have OPTG,k,Λ ≥ ApxOPT > 2krd (d-1) (r-k)ϵ . Next, using Claim 6, we have OPTG′ ,k,Λ > (1 - ϵ)OPTG,k,Λ and we are done.

Case 2: ApxOPT ≤ 2krd (d-1) (r-k)ϵ . In this case, we have OPTG,k,Λ ≤ e e-1 ApxOPT ≤ e e-1 2krd (d-1) (r-k)ϵ . Let ψ = ⌈ e e-1 2krd (d-1) (r-k)ϵ ⌉. We have for each v ∈ C, deg(v) < ψ/λmin; otherwise, v itself is a solution. We apply Reduction Rule 1

exhaustively with Wk + 1 = (ψ/λmin)k + 1. Let the final graph be G′ = (C ′ , V ′ ) where V ′ is obtained by deleting all the isolated vertices. By Proposition 3, we know that there are at most d((ψ/λmin)2k)d = ( dk ϵ )O(d2 ) vertices in C ′ . Now, we need to show that this is a (1 - ϵ)-APPA. By Lemma 4, we know that the application of Reduction Rule 1 does not change the optimum sco(·) value. Thus, we have OPTG′ ,k,Λ ≥ OPTG,k,Λ, which together with Lemma 10, implies that the reduction algorithm in Case 2 is also a (1-ϵ)- APPA.

This completes the proof of the lemma.

Reducing the Number of Voters

Lemma 12. (♣) Suppose that A is a parameter-preserving reduction algorithm for MAX SUBMOD-MWE that also preserves the set of candidates and OWA vectors, i.e, on input I = (G = (C, V), k,Λ), it produces I ′ = (G′ = (C, V ′ ), k,Λ). If there exists δ, h ≥ 0 and s > 0 (where h and s can depend on I) s.t. the following holds for any ksized subset X ⊆ C:

then, (A, Iden) is a (1, 2δ)-APPA.

Lemma 13. For any ϵ ∈ (0, 1), there is a parameterpreserving (1 - ϵ)-APPA for MAX SUBMOD-MWE when the profile graph is Kd,d-free, such that the output graph has the same set of candidates and O(k · d · nd+1 /ϵ) voters.

Proof. We abuse the notation and assume that we have (1, ϵ)- APPA. Here, 1 denotes a constant that is close but strictly less than one. This is done to derive the result in a cleaner manner. Then due to Proposition 8 and Lemma 9we have (1- ϵ (1- 1e ) )- APPAwhich is (1-ϵ′ )-APPA for ϵ′ = ϵ (1- 1e ) . Thus, to prove this lemma, it is sufficient to give an (1, ϵ)-APPA. On input I = (G, k, Λ), the reduction algorithm works as follows.

1. Use Lemma 9 to compute ApxOPT such that OPTI ≥ ApxOPT ≥ (1 - 1e )OPTI . Let s = ϵApxOPT k·10dnd .
2. Let Vset denote the subset of vertices in V with distinct neighborhoods, i.e., the set of voters with distinct approval list.
3. We start with V ′ being an empty multiset. For each v ∈ Vset, let mv denote the number of occurrences of v in V. We add ⌈mv/s⌉ copies of v to V ′ . We define graph G′ = (C, V ′ ).
4. We output I ′ = (G′ , k, Λ).

Since the degree of every vertex in C is at most OPTI/λmin, we have |V| ≤ nOPTI/λmin. Thus, by definition of V ′ ,

We claim that for every k-sized subset Y ⊆ C, we have |scoG(Y ) - s · scoG′ (Y )| ≤ ϵ2 OPTI. This, with Lemma 12 yields that (A, Iden) is a (1, ϵ)-APPA as desired.

To see that the claim holds, we observe that

Since G is Kd,d-free, therefore for every d-sized subset in C there can be at most d common neighbors in V. Thus the number of vertices in V with degree at least d is at most dnd . The number of vertices with unique neighborhood and with degree at most d is nd . Thus, we have

Towards the Kernel. On input (G, k,Λ), the reduction algorithm works as follows.

1. Apply (1 - ϵ2 )-APPA reduction from Lemma 11 to reduce the number of candidates.
2. Apply (1 - ϵ2 )-APPA reduction from Lemma 13 to reduce the number of voters.

The two steps ensure we get (1 - ϵ2 )2 -APPA. Since (1 - ϵ2 )2 ≥ (1 - ϵ), we have (1 - ϵ)-APPA. The first step reduces the number of candidates to ( dk ϵ )O(d2 ) . In the second step, the number of voters reduces to ( dk ϵ )O(d3 ) . Consequently, we obtain the following result.

Theorem 2. For any d ∈ N and ϵ ∈ (0, 1), there is a parameter preserving (1 - ϵ)-approximate kernel for MAX SUBMOD-MWE when the profile graph is Kd,d-free with ( dk ϵ )O(d2 ) candidates and ( dk ϵ )O(d3 ) voters.

5 Additive Parameterized Approximation

In this section, we design a one-additive parameterized approximation algorithm. In particular, we achieve the following: given a yes-instance I = (G, k, t,Λ) of SM-MWE, where G is a Kd,d-free graph, we output a committee of size k + 1 whose score is at least t, in time FPT in k + d + ϵ. Note that, we may return a (k + 1)-sized committee even for a no-instance. But, if the algorithm returns no, then I is a no-instance of SM-MWE.

We first give an intuitive description of the algorithm. If the candidate set C is bounded by g(k, d), then we can try all possible subsets to obtain a solution to I. If t is bounded by f(k, d), then observe that the degree of every vertex in C is bounded by f(k,d)/λmin, where λmin ≤ 1 is a constant; otherwise, a vertex of the highest degree is a solution to I. So, we apply Reduction Rule 1 with appropriately chosen W and bound the size of C by another function of k + d, and now again we can try all possible subsets of C. When none of the above cases hold, we either correctly return no or for a yes-instance, we find a committee of size k, say S′ , using Apx-MwE (Algorithm 1) for ϵ = λmin/4k (the choice of ϵ will be clear later). Recall that Apx-MwE returns a (1 - ϵ)- approximate solution, thus, scoΛG(S′ ) ≥ (1 - ϵ)t. We construct a large enough set of candidates (bounded by a function Algorithm 2 Add-Apx-MwE: An FPT algorithm for oneadditive approximation of MAX SUBMOD-MWE

Input: A bipartite graph G = (C, V, E), a set Λ = {λv : v ∈ V}, and non-negative integers k and t.

Output: Either a set S ⊆ C s.t. |S| ≤ k+1 and scoΛG(S) ≥ t,

or "no ".

• 1: if k = 0, t ≤ 0 then return an empty set.
• 2: if k = 0, t > 0 then return no
• 3: if |C| ≤ k(d-1)(4k2 )d-1 +1 then
• 4: if there exists a k-sized set S ⊆ C s.t. scoΛG(S) ≥ t then return S
• 5: else return no
• 6: if t ≤ 8k4dλmin then
• 7: apply Reduction Rule 1 exhaustively with W = t λmin ,
• 8: if there exists a set S ⊆ C s.t. scoΛG(S) ≥ t then return S
• 9: else return no
• 10: if Apx-MwE (G, k, t, ϵ = λmin 4k ,Λ) returns a set S′ then
• 11: Let H ⊆ C be a set of k(d - 1)(4k2λmin)d-1 + 1 candidates of highest score.
• 12: if there exists x ∈ H such that scoΛG({x} ∪ S′ ) ≥ t then return S′ ∪ {x}
• 13: else
• 14: for y ∈ H do
• 15: let Gy = (G \{y}) \(V0 ∪ V∅)
• 16: if Add-Apx-MwE (Gy, k - 1, t - scoΛG(y), Λy) returns a set S then return S ∪ {y}

of (k, d)) of high score, say H, and argue that, given a yesinstance, either every solution to I contains a vertex from H, or there is a vertex x in H such that scoΛG(S′ ∪ {x}) ≥ t.

Algorithm 2 describes the procedure formally. For x ∈ C, let us recall the definition of Λx. Firstly, for any OWA vector λv = {λv1 , λv2 , . . . , λv|Av| }, where v ∈ V, let λv-1 denote the OWA vector starting from the second entry, i.e., {λv2 , λv3 , . . . , λv|Av| }. Then Λx is the set ∪v∈N(x){λv-1 } ∪v∈B\N(x) {λv }, i.e., we delete the first entry of the OWA vectors of neighbors of x, and rest remains the same. Also, let V0 and V∅ denote the voters with all-zero vectors and empty vectors, respectively. We assume that our input instance does not contain any such voters.

We prove the correctness of Algorithm 2 in the following lemma.

Lemma 14. (♣) Given a yes-instance (G,Λ, k, t) of SMMWE, Algorithm 2 returns a Thiele Committee of size at most k + 1 whose score is at least t.

For proving Lemma 14, we establish a crucial result (in Lemma 17) that forms the core of our algorithm. Towards this, we first define a notion of High Degree Set as follows.

Definition 15. [Jain et al., 2023][β-High Degree Set] Given a bipartite graph G = (A, B, E), a set X ⊆ B, and a positive integer β > 1, the β-High Degree Set, is defined as:

Interestingly, the size of β-High Degree Set is bounded for Kd,d-free bipartite graphs as shown by the following.

Proposition 16. [Jain et al., 2023] For all d and for all β > 1 with |X| 2β > d, where X ⊆ B, if G = (A, B, E) is Kd,d-free, then |HDGβ (X)| ≤ f(β, d) = (d - 1)(2β)d-1 .

Next, we move towards proving the core result for our algorithm.

Lemma 17. (♣) Let (G,Λ, k, t) be an instance of SMMWE, where G is a Kd,d-free graph with V (G) = C ⊎ V. Let ℓ ≤ k and t′ ≤ t be two positive integers. Let S′ ⊆ C be an ℓ-sized set such that scoΛG(S′ ) ≥ t′ (1 - λmin 4ℓ ), where t′ ≥ 8ℓ4dλmin, and H be a set of ℓ(d - 1)(4ℓ2λmin)d-1 + 1 highest score candidates in C. For any S ⊆ C of size ℓ with scoΛG(S) ≥ t′ , either S ∩ H ̸= ∅ or there exists a candidate x ∈ H such that scoΛG({x} ∪S′ ) ≥ t′ . If there exists a vertex v of degree at least t′ λmin , then S′ = {v}.

Running Time: The running time of the algorithm is governed by the following recurrence relation

1. T(k) ≤ (k(d - 1)(4k2λmin)d-1 + 1) · T(k - 1) + (kd)O(kd) + (k(d - 1)(4k2λmin)d-1 + 1)k+1nO(1) + ( dk ϵ )O(d2 k) nO(1) (where ϵ = λmin 4k ).

This is because in the first three cases the algorithm takes time (kd)O(kd) , (k(d - 1)(4k2λmin)d-1 + 1)k+1nO(1) , and (dk)O(d2 k)nO(1) respectively. Solving the recurrence, we get T (k) ≤ (dk)O(d2 k)nO(1) .

Theorem 3. There exists an algorithm for SM-MWE that runs in time (dk)O(d2 k)nO(1) , and returns a set S ⊆ A of size at most k + 1 such that scoG(S) ≥ t.

6 Outlook

In this paper, we modeled the MULTIWINNER ELECTION problem as a graph-theoretic problem which enables us to address the problem in the Kd,d-free graph class. This approach captures a broader range of profiles than that of [Skowron, 2017]. Specifically, it generalizes the class of bounded approval sets, a class that admits tractable results. For SMMWE, we developed an FPT-AS and a lossy polynomialtime preprocessing procedure. To the best of our knowledge, our additive approximation algorithm and lossy preprocessing method represent novel technical contributions to the field of computational social choice theory.

Our work is just a starting point in this area, with several potential extensions. In our algorithm, we assumed that the functions are both monotone and submodular. A natural question is what happens if we relax one of these constraints. Additionally, while we focused on the approval model of elections, the next logical step is to extend our investigations to ordinal or cardinal elections. Another direction would be to incorporate fairness or matroid constraints into the voting profiles, as explored in [Inamdar et al., 2024]. Also considering diversity constraints on selected committee as studied in [Bredereck et al., 2018] could be another direction of future work.

Acknowledgements

Sushmita Gupta and Pallavi Jain acknowledges their support from SERB-SUPRA grant number SPR/2021/000860. Sushmita Gupta also acknowledges support from SERB's MATRICS grant (MTR/2021/000869). Pallavi Jain also acknowledges support from IITJ Seed Grant grant I/SEED/PJ/20210119. Saket Saurabh is supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 819416).