Paper deep dive
Algorithms for Structured Elections under Thiele Voting Rules
Alexandra Lassota, Krzysztof Sornat
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/3/2026, 10:23:47 AM
Summary
This paper investigates the computational complexity of winner determination in approval-based committee elections under Thiele voting rules, focusing on Proportional Approval Voting (PAV). The authors introduce a structural characterization of optimal committees based on a dominance relation among candidates, where a candidate dominates another if its set of supporters strictly contains the other's. Using this structure, they develop Fixed-Parameter Tractable (FPT) algorithms for Thiele rules on the Voter Interval (VI) domain, parameterized by the maximum number of approvals per candidate and per voter. Additionally, they resolve open questions by providing polynomial-time algorithms for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of the winning committee.
Entities (7)
Relation Signals (6)
Thiele voting rules → includes → Proportional Approval Voting
confidence 98% · These form a class of rules parameterized by a fixed weight vector... Proportional Approval Voting (PAV) as a prominent member
Thiele voting rules → includes → Chamberlin-Courant Approval Voting
confidence 97% · For instance, Chamberlin-Courant Approval Voting (CC) [CC83] promotes diversity
Thiele voting rules → iscomputationallyhard → NP-hard
confidence 96% · computing a winning committee under Thiele rules is computationally challenging. In fact, finding a winning committee under any non-trivial Thiele rule... is NP-hard.
FPT algorithms → appliesto → Voter Interval domain
confidence 95% · we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval (VI) domain
dominance relation → characterizes → optimal committees
confidence 94% · We provide a structural characterization of optimal committees under Thiele rules based on a dominance relation among candidates.
Yang and Wang → posed → open problems
confidence 90% · resolving two open problems posed by Yang and Wang [YW18, YW23]
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate---that is, how voters' approval ballots induce dependencies between candidates---revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval (VI) domain---that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on VI is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.
Tags
Links
- Source: https://arxiv.org/abs/2607.28575v1
- Canonical: https://arxiv.org/abs/2607.28575v1
Trouble viewing inline? Open PDF directly →
Full Text
63,982 characters extracted from source content.
Expand or collapse full text
Algorithms for Structured Elections under Thiele Voting Rules111A conference version of this work appeared in AAAI 2026 [LS26]. Alexandra Lassota TU Eindhoven, the Netherlands a.a.lassota@tue.nl Krzysztof Sornat AGH University, Poland sornat@agh.edu.pl Abstract We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter’s satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate—that is, how voters’ approval ballots induce dependencies between candidates—revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval (VI) domain—that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on VI is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee. 1 Introduction Multi-winner elections based on approval ballots are used in many settings, such as recommendation systems, committee selection, and blockchain [SFL16, LS23, BBC+24], where every voter expresses its preferences as a subset of candidates it approves of. A central family of voting rules for such applications are Thiele rules [THI95], which include Proportional Approval Voting (PAV) as a prominent member [AGG+15]. These rules balance diversity, proportionality, and excellence in the selected committee, depending on the specific Thiele rule used [LS21]. For instance, Chamberlin-Courant Approval Voting (C) [C83] promotes diversity by ensuring broad representation; PAV aims for proportional representation, satisfying strong proportionality axioms like EJR+ [BP23]; Multi-winner Approval Voting focuses on excellence by selecting the most approved candidates. However, computing a winning committee under Thiele rules is computationally challenging. In fact, finding a winning committee under any non-trivial Thiele rule (i.e., every rule except for Multi-winner Approval Voting) is NP-hard. For C and PAV, the problems remain NP-hard even under very restricted conditions where each candidate is approved by exactly 3 voters and each voter approves exactly 2 candidates [AGG+15, SFL16]. To better understand and overcome this computational hardness, a natural direction is to restrict the input domain. Such restrictions often enable polynomial-time algorithms for otherwise intractable rules, and this approach has been particularly fruitful in approval-based committee elections. Two central restricted domains for approval ballots are the Candidate Interval (CI) and the Voter Interval (VI) domains [ELP17, ELP25]. In the CI domain, candidates can be ordered so that each voter’s approval set forms a contiguous interval. CI captures scenarios where candidates are linearly ordered, e.g. by ideology or location, and each voter is focused on a specific region of the spectrum. One key advantage of CI is that it allows the winner determination problem for all Thiele rules to be solved efficiently. It is by using an integer linear programming formulation that admits a totally unimodular constraint matrix, which are known to be solvable in polynomial time [PET18, PL20]. The VI domain, in contrast, imposes structure on the voters rather than on the candidates. Here, voters can be ordered so that each candidate is approved by a consecutive segment of voters. This domain models scenarios where voters are structured by demographic or socioeconomic features such as age, income, or education level, and candidates appeal to specific groups, e.g. young voters, low-income households, or university-educated individuals. The VI domain has received significant attention [ELP17, ELP25] and, consequently, for several voting rules, such as C, Monroe’s and Minimax Approval Voting polynomial-time winner-determination algorithms for VI elections are known [BSU13, LG16]. Yet, for most Thiele rules, and PAV in particular, the computational complexity of winner determination on VI remains a prominent open question [ELP17, PET18, GBS+21, LS23, ELP25]. Despite the dual nature of the VI and CI domains, the techniques used for CI do not translate to VI. In particular, the constraint matrix of the integer linear programming formulation is not totally unimodular anymore under VI preferences and, thus, it is not clear whether this problem can be solved in polynomial time or not. This motivates a search for new structural results and algorithmic techniques. Structural Results. This work takes a new approach to understand the computational complexity of Thiele rules by studying the structure of winning committees. Instead of considering candidates in isolation, we examine how shared support among voters constrains the possible combinations of candidates in a winning committee. We provide a structural characterization of optimal committees under Thiele rules based on a dominance relation among candidates. Specifically, a candidate c is said to dominate another candidate d if the set of supporters of c strictly contains that of d. This induces a hierarchy of dominancy levels where candidates within the same level do not dominate one another and each is dominated by some candidate in a higher level. We show that there always exists a winning committee that is non-dominated, meaning that no member is dominated by any candidate outside the committee. These structural insights apply to general approval profiles and are of independent interest, offering new theoretical tools for analyzing and determining winners under Thiele rules. Practically, this structure can guide the development of more efficient algorithms and heuristics. Theoretically, it offers a new perspective on the open question of whether winner determination under PAV is polynomial-time solvable on VI. Algorithmic Results. We show that our structural insights are particularly effective when combined with the VI property: candidates of a VI instance can be partitioned into parts such that candidates within a part influence only a limited number of voters. This allows to design a dynamic program over a sequence of such parts, exploiting the limited interaction. As a result, we obtain an FPT algorithm for PAV and, more generally, for any Thiele rule, when parameterized by two parameters combined: the maximum number of approvals received by a candidate, and the maximum number of approvals in a vote. Notably, the same parameterization is para-NP-hard in the general (unstructured) case—that is, the problem remains NP-hard even when both parameters are constants. This contrast highlights the algorithmic power of our structural approach and provides substantial progress toward resolving the open question on the complexity of PAV in the VI domain [ELP17, PET18, LS23, ELP25]. Beyond the VI setting, we further contribute to understanding tractable cases for Thiele rules by resolving two open problems posed by Yang and Wang [YW18, YW23], originally asked for PAV: (1) we provide a polynomial-time algorithm for instances where each candidate is approved by at most two voters, based on a proper integer linear programming formulation; and (2) we give an FPT algorithm parameterized by the total score of a winning committee, employing combinatorial tools like color-coding and splitters. It is particularly interesting as the score may not be integer. Moreover, this parameter can be smaller than the number of voters for which FPT algorithms exist. Importantly, our results extend to all Thiele rules, not just PAV, demonstrating the generality of our approach. Structure of the Paper. Section˜2 introduces notation for the approval-based committee election model, structured domains and voting rules studied in this paper. Section˜3 presents our structural results on winning committees under Thiele rules. Section˜4, using the structural results, develops an FPT algorithm on VI instances. In Section˜5, we give an FPT algorithm parameterized by the total score of the optimal committee, and a polynomial-time algorithm for instances where each candidate is approved by at most two voters. 1.1 Related Work Recently, another FPT algorithm parameterized by the total score of a winning committee was provided independently by Gupta, Jain, Saha, Saurabh and Upasana [GJS+25]. Even though they also use color-coding at the heart of their algorithm, the approaches differ significantly: while they color candidates and voters, we color the approvals of the voters. This results in a different number, type, and meaning of guesses, as well as a different construction of the overall solution. It also results in differences in running times. While the algorithms outperform each other in some cases, our algorithm runs in time truly linear in the number of voters, which we see as a strong advantage. For more detailed discussion about differences between both algorithms, as well as quantitative comparison of running times, we defer to Section˜5.2. There is also a substantial body of work on tractability of voting rules under restricted domains in the ordinal setting (in which voters cast votes in a form of linear orders over candidates), such as Single-Peaked (SP) and Single-Crossing (SC) preferences. These domains are the ordinal counterparts of CI and VI, respectively, and have led to efficient algorithms for many voting rules, including C (in its general version defined on cardinal values of misrepresentation) and Kemeny. In particular, a classic dynamic programming algorithm was proposed for C by Betzler et al. [BSU13]. More recently, an algorithm with near linear-time in the input size has been developed for the case where the SC-axis (ordering of voters) or the SP-axis (ordering of candidates) is explicitly given [CE21, SVX22]. These works illustrate the general principle that structural properties of preferences can be algorithmically exploited. For more information about these and other restricted domains see, e.g., the works of Elkind, Lackner and Peters [ELP17, ELP25]. Parameterized Complexity of Thiele Rules. For an overview of the parameterized complexity of Thiele rules, we refer to the recent work by Yang and Wang [YW23], who provide a comprehensive summary of known results (see Table 1 therein), along with new findings for several structural parameters and their combinations. Below, we briefly discuss the main results for standard parameters such as the number of voters n, the number of candidates m, and the committee size k, with an emphasis on the techniques used and known lower bounds. A trivial brute-force algorithm checking total scores of all size-k subsets of candidates runs in FPT time with respect to m, namely O∗(2m)O^*(2^m). This is essentially optimal for every non-constant Thiele rule, as under the Exponential Time Hypothesis there is no O∗(2o(m))O^*(2^o(m))-time algorithm for this problem [SVX22]. A mixed integer linear program (MILP) presented by Faliszewski et al. [FSS+18, Fig. 2] implies an FPT algorithm with respect to n for every Thiele rule.222Even though ordinal ballots and top-k-counting rules are considered in the MILP [FSS+18, Fig. 2], it is enough to replace gm,k(j)g_m,k(j) with wjw_j, where wjw_j is the j-th element of the Thiele sequence w, and to adjust the definition of (Si)T(S_i) to the set of candidates approved by voters from SiS_i and no voter from V∖SiV S_i. The main idea is to define an integer variable for each candidate type (defined by its set of supporters; hence, there are at most 2n2^n types), which encodes how many candidates of a particular type are selected for the solution. Non-integral variables are forced to take integral values in the optimal solution, as first used by Bredereck et al. [BFN+15]. The resulting running time is double-exponential, namely O∗(22O(n))O^*(2^2^O(n)) [BFK+20a]. A single-exponential lower bound of O∗(2o(n))O^*(2^o(n)) under the Exponential Time Hypothesis is known [SVX22], hence, there is still a significant gap remaining. A similar MILP idea has been applied in many contexts, e.g., for extensions of Thiele rules [JST20, YW23], as well as for problems related to bribery and control in elections [BFN+20b]. Every non-constant Thiele rule is also W[1]-hard with respect to the committee size [AGG+15, JST20, SVX22]. Approximability of Thiele Rules. Thiele rules have also been studied from the perspective of approximability, where the goal is to compute a committee whose total score is close to optimal [SFL16, BSS18]. For a broad class of Thiele rules, tight polynomial-time approximation algorithms have been established [DMM+20, BFF21, BFG+22]. 2 Preliminaries We are given a set of candidates C=c1,c2,…,cmC=\c_1,c_2,…,c_m\ and a set of voters V=v1,v2,…,vnV=\v_1,v_2,…,v_n\. Each voter v∈Vv∈ V expresses its preference in the form of an approval set Av⊆CA_v C, and the collection A=(Av)v∈VA=(A_v)_v∈ V is referred to as an approval profile. Any subset of C is called a committee. We write k≔W⊆C:|W|=kW_k \W C:|W|=k\ to denote the set of all committees of size k. For a candidate c∈Cc∈ C, we denote by Vc≔v∈V:c∈AvV_c \v∈ V:c∈ A_v\ the set of supporters of c. We extend the notation to sets of candidates C′⊆C C, i.e., VC′≔⋃c∈C′VcV_C _c∈ C V_c. We define ΔC≔maxc∈C|Vc| _C _c∈ C|V_c| as the maximum number of approvals given to a candidate and ΔV≔maxv∈V|Av| _V _v∈ V|A_v| as the maximum number of approved candidates by a voter. An approval-based committee (ABC) election is a tuple E=(C,V,A,k)E=(C,V,A,k). A voting rule is a function taking an election as an input and outputs a set of winning committees of size k. The w-Thiele voting rule [THI95] is parameterized by a non-increasing infinite sequence w=(w1,w2,…)w=(w_1,w_2,…), called a Thiele sequence. Given an election (C,V,A,k)(C,V,A,k), a committee W∈kW _k is optimal under the w-Thiele rule if it maximizes the total score: d≔scorew(W)=∑v∈V∑i=1|Av∩W|wi, d _w(W)= _v∈ V _i=1^|A_v∩ W|w_i, over all committees of size k. The w-Thiele rule returns the set of all such optimal committees. The corresponding computational problem w-Thiele requires outputting a single optimal committee. Its decision variant asks whether there exists a committee of size k with a total score at least a given value. All Thiele rules considered in the literature are defined with w1=1w_1=1 (see examples below). Dividing w by w1w_1 and obtaining w1=1w_1=1 does not affect either its set of optimal solutions or its approximability [DMM+20], but it affects the parameter d, the total score of an optimal solution that is studied in this paper. In particular, if we allow w1≤1kw_1≤ 1k, then d≤ΔC⋅k⋅1k=ΔCd≤ _C· k· 1k= _C, but every w-Thiele with non-constant w is NP-hard even if ΔC=3 _C=3 [AGG+15, SFL16], so this would imply paraNP-hardness with respect to d. Therefore, we use the standard normalization w1=1w_1=1 in this paper. (However any algorithm with running time dependent on d after such normalization becomes an algorithm with running time dependent on d+1w1d+ 1w_1.) Arguably, three most prominent w-Thiele rules are: • Chamberlin-Courant Approval Voting (C), that is w-Thiele with w=(1,0,0,…)w=(1,0,0,…). • Proportional Approval Voting (PAV), that is w-Thiele with wj=1jw_j= 1j. • Multi-winner Approval Voting (AV), that is w-Thiele with w=(1,1,1,…)w=(1,1,1,…). An interpolation between C and AV is ℓ -Coverage that is w-Thiele with wj=1w_j=1 for j≤ℓj≤ and wj=0w_j=0 otherwise [BFG+22]. Generalized Thiele is a voting rule [SVX22] which takes as an input an election (C,V,A,k)(C,V,A,k) and n Thiele sequences represented as w:V×ℕ→[0,1]w V×N→[0,1], where (wiv)i∈ℕ(w^v_i)_i is a Thiele sequence for a voter v∈Vv∈ V, and outputs a committee W∈kW _k which maximizes the total score: d≔scorew(W)=∑v∈V∑i=1|Ai∩W|wiv,d _w(W)= _v∈ V _i=1^|A_i∩ W|w^v_i, over all committees of size k. Naturally, Generalized Thiele where wv=wv′w^v=w^v for v,v′∈Vv,v ∈ V is equivalent to wvw^v-Thiele. Definition 1 (Voter Interval). An approval profile A has Voter Interval (VI) property if there exists a linear order of voters such that for every candidate c∈Cc∈ C, the set VcV_c is an interval on the linear order. An analogous restricted domain is defined for ordering of candidates. Definition 2 (Candidate Interval). An approval profile A has Candidate Interval (CI) property if there exists a linear order of candidates such that for every voter v∈Vv∈ V, the set AvA_v is an interval on the linear order. If an approval profile is VI, then a corresponding ordering of voters—called a VI-axis—can be found in polynomial time; thus, we assume w.l.o.g. that the ordering is (v1,v2,…vn)(v_1,v_2,… v_n). An analogous ordering for CI profiles can be found also in polynomial time [FHH+11, EL15]. We write [n]=1,2,…,n[n]=\1,2,…,n\ and adopt standard notation from computational and parameterized complexity theory [CFK+15]. In particular, a decision problem parameterized by k is fixed parameter tractable (FPT) with respect to k if it can be solved in time f(k)⋅poly(|ℐ|)f(k)·poly(|I|) for any instance (ℐ,k)(I,k), where f is a computable function and |ℐ||I| denotes the input size. A problem solvable in time |ℐ|f(k)|I|^f(k) belongs to the class XP, which implies it is solvable in polynomial time for any fixed value of k. The notation O∗(⋅)O^*(·) suppresses factors polynomial in the input size. 3 Structure of Winning Committees For a given approval profile A, we create the dominancy graph of A where vertices correspond to candidates and a directed edge from c to c′c exists if Vc′⊂VcV_c ⊂ V_c, i.e., a candidate c′c is dominated by c (all supporters of c′c are also supporters of c, and c has a supporter not supporting c′c ). This dominancy relation coincides with the one recently introduced independently by Dong et al. [DBW+25]. Non-dominated candidates are those candidates that have no incoming edge in the dominancy graph, we denote this set as L1L_1. We partition C into dominancy levels L1,…,LδL_1,…,L_δ such that every candidate c∈Lic∈ L_i is at distance exactly i in G from some candidate in L1L_1 and there is no candidate c′∈L1c ∈ L_1 such that the distance in the dominancy graph between c′c and c is strictly smaller than i. We denote by δ the depth of a dominancy graph. By the definition of dominancy relation involving strict inclusion, we have δ≤ΔC+1δ≤ _C+1. Definition 3. A committee W⊆CW C is non-dominated if every candidate belonging to any directed path from an element of L1L_1 to an element of W also belongs to W. The next theorem characterizes optimal solutions to Generalized Thiele with respect to non-dominancy. Theorem 4. There exists an optimal solution to Generalized Thiele that is non-dominated. Furthermore, if wiv>wi+1vw_i^v>w_i+1^v for all v∈Vv∈ V and all i∈ℕi , then every optimal solution to Generalized Thiele must be non-dominated. Proof. Let E be an instance of Generalized Thiele. Let W be an optimal solution to Generalized Thiele on E. We can modify W until it becomes non-dominated: considering a directed path P=(p1,…,p|P|)P=(p_1,…,p_|P|) of maximum length such that p1∈L1,p|P|∈Wp_1∈ L_1,p_|P|∈ W and pi∉Wp_i∉ W for some i∈1,…,|P|−1i∈\1,…,|P|-1\, we replace W with (W∖P)∪pi:i∈1,…,|W∩P|(W P)∪\p_i:i∈\1,…,|W∩ P|\ which has the same cardinality as W. We repeat this procedure until W is non-dominated. This must happen after a finite number of steps, as by considering paths P of maximum length ℓ∈[δ] ∈[δ], after at most k steps (considering at most all elements of W), every candidate from W being at distance ℓ from L1L_1 is dominated only by candidates from W. By continuing the procedure over a decreasing index of dependency layers, after at most k^k steps, every path from L1L_1 to W is included in W. Observe that the final W has a total score at least as high as the initial optimal committee because each replacement of candidates in the procedure does not decrease the score of any voter as each voter gets at least the same amount of candidates approved per definition of the dominancy graph. The second claim holds, as if any optimal solution W is dominated, then by making a replacement of candidates on a path P from L1L_1 to W, such that P∖W≠∅P W≠ as done in the procedure, we produce a new solution of size k with strictly higher total score which would be a contradiction to the optimality of W. ∎ Theorem˜4 has several useful implications. To solve Generalized Thiele, it suffices to consider only the first k dominancy levels. Indeed, for any c∈Lk+1∪⋯∪Lδc∈ L_k+1∪…∪ L_δ and any size-k committee containing c, there exists a candidate c′∈L1∪⋯∪Lkc ∈ L_1∪…∪ L_k outside the committee that dominates c. Proposition 5. There exists an optimal solution to Generalized Thiele that is a subset of L1∪⋯∪LkL_1∪…∪ L_k. For specific Thiele rules, the instances might be even further restricted. For example, in ℓ -Coverage, the score of a voter v from committee W equals min|Av∩W|,ℓ \|A_v∩ W|, \. This means that a voter can receive score at most ℓ , which implies that only dominancy levels L1,…,LℓL_1,…,L_ are of interest because removing candidates from levels Lℓ+1,…,LδL_ +1,…,L_δ from a solution does not change its total score. In the case |L1∪⋯∪Lℓ|<k|L_1∪…∪ L_ |<k, by taking all candidates from L1∪⋯∪LℓL_1∪…∪ L_ to the committee, we obtain a solution with the total score equal to scorew(C)score_w(C) (we fill the remaining seats in the committee with arbitrary candidates). Hence, in the case of ℓ -Coverage, we may assume w.l.o.g. that δ≤ℓδ≤ . In general, the above discussion implies the following. Proposition 6. There exists an optimal solution to Generalized Thiele that is non-dominated and that is either a subset or a superset of L1∪⋯∪LℓL_1∪…∪ L_ , where ℓ=argmaxi∈ℕ(∃v∈V(wiv>0)) = *arg\,max_i ( _v∈ V(w_i^v>0) ). Further structural results, specialized for the VI domain, are developed in the proof of Theorem˜7. 4 FPT Results on Voter Interval The following result shows that Generalized Thiele on VI is FPT parameterized by ΔC+ΔV _C+ _V. Note that Generalized Thiele on general instances is NP-hard even if ΔC=3 _C=3 and ΔV=2 _V=2, and the hardness persists even for PAV and for C, which are special cases of Generalized Thiele [AGG+15, SFL16]. This shows that the problem is easier to solve in the VI domain assuming P≠ (a standard assumption in computational complexity theory). This result progresses towards resolving the central open question on the complexity of PAV in the VI domain. Theorem 7. Generalized Thiele on the Voter Interval domain is FPT parameterized by ΔC+ΔV _C+ _V and is XP parameterized by ΔC _C. Proof. Due to having VI preferences with respect to (v1,…,vn)(v_1,…,v_n), for every candidate c∈Cc∈ C, we have Vc=vi,vi+1,…,vjV_c=\v_i,v_i+1,…,v_j\ for some 1≤i≤j≤n1≤ i≤ j≤ n (w.l.o.g., we assumed there are no candidates with an empty set of supporters). We denote by min(Vc) (V_c) and max(Vc) (V_c) the indices of the first and, respectively, the last supporting voters of candidate c. We order the candidates (c1,…,cm)(c_1,…,c_m) such that for every pair of indices i<ji<j, one of the following conditions holds: (1) max(Vci)<max(Vcj) (V_c_i)< (V_c_j), or (2) max(Vci)=max(Vcj) (V_c_i)= (V_c_j) and min(Vci)<min(Vcj) (V_c_i)< (V_c_j). For each i∈[n]i∈[n], we define the set Ci=c∈C:max(Vc)=iC_i=\c∈ C: (V_c)=i\, called a triangle. Each triangle CiC_i consists of candidates with the same last supporting voter viv_i. Note that C1,…,Cn\C_1,…,C_n\ is a partition of C. The term triangle comes from the visual shape of the approval set of candidates in CiC_i when the approval profile is displayed as a matrix. In particular, after applying the above candidate ordering (c1,…,cm)(c_1,…,c_m), where candidates in CiC_i appear consecutively, and arranging the voters according to the VI-axis, the approvals form triangular patterns, as shown in Figure˜1. We denote by min(Ci) (C_i) and max(Ci) (C_i) the indices of the first and, respectively, the last candidate included in CiC_i. c1c_1 c2c_2 c3c_3 c4c_4 c5c_5 c6c_6 v1v_1 ✓ v2v_2 ✓ ✓ ✓ v3v_3 ✓ ✓ ✓ ✓ v4v_4 ✓ ✓ ✓ Figure 1: An example of a VI approval profile, where the voters are ordered according to the VI-axis, and the candidates are ordered as described in the proof of Theorem˜7. In this example, there are two non-empty triangles: C3=c1,c2,c3C_3=\c_1,c_2,c_3\ and C4=c4,c5,c6C_4=\c_4,c_5,c_6\. Triangle C3C_3 is associated with voter v3v_3, meaning that each candidate in C3C_3 has v3v_3 as their last supporter. For instance, c1∈C3c_1∈ C_3 because max(Vc1)=3 (V_c_1)=3. The collective set of supporters of C4C_4 is VC4=v2,v3,v4V_C_4=\v_2,v_3,v_4\. We have min(C4)=4 (C_4)=4 and max(C4)=6 (C_4)=6. Due to Theorem˜4, let us consider a fixed non-dominated solution WOPTW_OPT. It holds that WOPT∩CiW_OPT∩ C_i is a subset of candidates from CiC_i having indices exactly min(Ci),…,j\ (C_i),…,j\ where j=min(Ci)+|WOPT∩Ci|−1≤max(Ci)j= (C_i)+|W_OPT∩ C_i|-1≤ (C_i). In other words, any optimal solution contains a (possibly empty) prefix of every triangle CiC_i. The number of all possible committees consisting of prefixes of the triangles might still be exponential in n. We solve the problem via a dynamic program. It iterates over some order of the triangles C1,…,CnC_1,…,C_n and considers prefixes of CiC_i based on prefixes taken so far to a solution of a limited number (in terms of the parameters) of preceding triangles. A crucial observation is that candidates from triangle CiC_i have common supporters with at most O(ΔV⋅ΔC)O( _V· _C) many candidates outside of CiC_i. This allows for making “local” decisions when considering candidates from a triangle CiC_i, where the size of locality is defined in terms of the parameters. More formally, let VCiV_C_i be the set of voters supporting any candidate from CiC_i (hence, |VCi||V_C_i| is the height of a triangle CiC_i). We observe that |VCi|≤ΔC|V_C_i|≤ _C, as all members of CiC_i have the i-th voter as the last supporter and the maximum number of approvals received by a candidate is ΔC _C. Hence, we can write VCi⊆max(VCi)−ΔC,…,max(VCi)V_C_i \ (V_C_i)- _C,…, (V_C_i)\. We have |Ci|≤ΔV|C_i|≤ _V, as every candidate in CiC_i is supported by viv_i. Thus, overall, the size of every triangle is bounded in terms of the parameters of our instance. We base our dynamic program table T[a,b,d1,…,d|VCb|]T[a,b,d_1,…,d_|V_C_b|] on these observations: the table saves the maximum total score of Generalized Thiele of a (non-dominated) committee of size a taken from the first b triangles (that is, from C1∪⋯∪CbC_1∪…∪ C_b) such that the i-th voter from VCbV_C_b approves exactly did_i committee members. As our goal is finding a committee, we will also store (only) one committee that achieves a particular score in table T. We initialize the table with the first triangle, that is, for b=1b=1, we fill exactly min|C1|,k+1 \|C_1|,k\+1 entries of T[a,1,d1,…,d|VC1|]T[a,1,d_1,…,d_|V_C_1|] by considering committees C1(a)C_1(a) being a prefix of C1C_1 of size a. Formally, C1(0)=∅C_1(0)= and C1(a)=cmin(C1),…,cmin(C1)+a−1C_1(a)=\c_ (C_1),…,c_ (C_1)+a-1\ for a∈ℕ:a≤min|C1|,ka :a≤ \|C_1|,k\. By di(a)d_i(a) we denote the number of approved candidates by i-th voter from VC1V_C_1 in a committee C1(a)C_1(a). We store the total score achieved by a committee C1(a)C_1(a) in a corresponding entry of T[a,1,d1(a),…,d|VC1|(a)]T[a,1,d_1(a),…,d_|V_C_1|(a)]. When iterating over b>1b>1, we will consider committees Cb(a)C_b(a) for 0≤a≤min|Cb|,k0≤ a≤ \|C_b|,k\ being merged with every committee stored in non-empty entries created in the previous step, i.e., when considering solution up to (b−1)(b-1)-th triangle. Formally, we take a committee WtempW_temp from every non-empty cell of T[|Wtemp|,b−1,d1temp,…,d|VCb−1|temp]T[|W_temp|,b-1,d_1^temp,…,d_|V_C_b-1|^temp] and we create a new committee Wtemp∪Cb(a)W_temp∪ C_b(a) for every a such that 0≤a≤min|Cb|,k−|Wtemp|0≤ a≤ \|C_b|,k-|W_temp|\. Note that in this way |Wtemp∪Cb(a)|≤k|W_temp∪ C_b(a)|≤ k. Now, we compare the score of Wtemp∪Cb(a)W_temp∪ C_b(a) with a score of a committee of respective entry of T, i.e., T[|Wtemp|+a,b,d1(a,Wtemp),…,d|VCb|(a,Wtemp)]T[|W_temp|+a,b,d_1(a,W_temp),…,d_|V_C_b|(a,W_temp)], where di(a,Wtemp)d_i(a,W_temp) is the number of approved candidates by the i-th voter from VCbV_C_b in the committee Wtemp∪Cb(a)W_temp∪ C_b(a). If Wtemp∪Cb(a)W_temp∪ C_b(a) achieves a strictly higher score, i.e. score(Wtemp∪Cb(a))>T[|Wtemp|+a,b,d1(a,Wtemp),…,d|VCb|(a,Wtemp)]score(W_temp∪ C_b(a))>T[|W_temp|+a,b,d_1(a,W_temp),…,d_|V_C_b|(a,W_temp)], then we update the entry with this higher score, and we store Wtemp∪Cb(a)W_temp∪ C_b(a) as a committee achieving this score. We note that the procedure is well-defined also in the case of Cb=∅C_b= because the only prefix of CbC_b considered will be an empty set. To obtain the maximum total score committee, we search for the largest value among non-empty entries of T[k,n,d1,…,d|VCn|]T[k,n,d_1,…,d_|V_C_n|]. The correctness of the dynamic program follows from the fact that every such entry stores a valid committee of size k, and, as argued before, the optimal committee WOPTW_OPT satisfies WOPT∩Ci=Ci(|WOPT∩Cb|)W_OPT∩ C_i=C_i(|W_OPT∩ C_b|), i.e., WOPTW_OPT consists of prefixes of the triangles CiC_i. This implies that, for every b∈[n]b∈[n], the table entry T[|WOPT∩(∪i∈[b]Ci)|,b,d1(b),…,d|VCb|(b)]T[|W_OPT∩( _i∈[b]C_i)|,b,d_1(b),…,d_|V_C_b|(b)] stores a committee whose total score is at least scorew(WOPT∩∪i∈[b]Ci)score_w(W_OPT∩ _i∈[b]C_i) because the relevant triangle prefixes Ci(|WOPT∩Ci|)C_i(|W_OPT∩ C_i|) (or any other prefixes yielding the same score and satisfying each voter in VCbV_C_b by the same number of approved committee members) were explicitly considered during the construction of this entry. Together with the base case, i.e., filling the entries T[a,1,d1,…,d|VC1|]T[a,1,d_1,…,d_|V_C_1|], this completes an inductive argument for the correctness of the algorithm. The size of T is at most O(k⋅n⋅ΔVΔC)O(k· n· _V _C). In order to fill all entries for particular b∈[n]b∈[n], we consider at most k+1k+1 prefixes of b-th triangle merged with every committee stored in a non-empty cell of T with b−1b-1. Therefore, we consider at most O(k2⋅ΔVΔC)O(k^2· _V _C) many committees, each in polynomial time. In total, this gives a running time of O∗(ΔVΔC)O^*( _V _C) which is FPT with respect to ΔC+ΔV _C+ _V. ∎ A consequence from the above presented proof is an FPT algorithm parameterized by ΔC+k _C+k. That is, the indices of T, which encode how many times every voter involved is represented, never exceed the committee size k. Corollary 8. Generalized Thiele on the Voter Interval domain can be solved in O∗(kΔC)O^*(k _C) time. We note that Theorem˜14 provides an FPT algorithm parameterized by ΔC+k _C+k for every instance, but its running time is double-exponential on k in contrast to the non-exponential dependence on k in the case of VI (Corollary˜8). It is another example of parameterization for which much more efficient algorithms exist for the VI structured domain. 5 FPT Results on General Instances In the next two subsections, we present two FPT algorithms for Generalized Thiele which answer affirmatively two open questions known in the literature [YW18, YW23], which were asked for a special case of PAV. In Section˜5.1 we provide a polynomial-time algorithm for instances with ΔC=2 _C=2. In Section˜5.2 we give an FPT algorithm parameterized by the total score of an optimal committee. 5.1 Polynomial-Time Algorithm when ΔC=2 _C=2 Our polynomial-time algorithm for Generalized Thiele with ΔC=2 _C=2 is based on a generalization of an integer linear program (ILP) studied by Peters [PET18]. The ILP formulation in [PET18] is defined for any w-Thiele, but it can be easily adjusted to Generalized Thiele by modifying the objective function [SVX22]. For a given election (C,V,A,k)(C,V,A,k) the ILP for Generalized Thiele (ILP-GT) is defined as follows, where roughly speaking, the ycy_c variables mark selected candidates, the xv,ix_v,i variables track voter satisfaction levels and the objective ensures that the highest available values in a Thiele sequence are always chosen: maximize∑v∈V∑i∈[k]wiv maximize _v∈ V _i∈[k]w^v_i ⋅xv,i · x_v,i (ILP-GT) subject to∑c∈Cyc subject to 3.0pt _c∈ Cy_c =k =k (1) ∑i∈[k]xv,i _i∈[k]x_v,i ≤∑c∈Avyc∀v∈V ≤ _c∈ A_vy_c \;∀ v∈ V (2) xv,i x_v,i ∈0,1∀v∈V,i∈[k] ∈\0,1\ ∀ v∈ V,i∈[k] yc y_c ∈0,1∀c∈C ∈\0,1\ 1.0pt∀ c∈ C Peters [PET18] showed that the constraint matrix of ILP-GT is totally unimodular (TU) when an approval profile is CI, hence an optimal solution can be found in polynomial time. He actually argued that if an approval profile A captured as a matrix, one can find an optimal solution in polynomial time even when an additional row with all-11s is appended (corresponding to Constraint (1)), as the resulting matrix is still TU. In the case of A being CI, total unimodularity was an immediate implication from the fact that A being CI has consecutive one property, and because the additional row consists of only 11s (hence, it is consistent with the consecutive 11s property). In the case where A is VI, total unimodularity is not necessarily preserved. While the transpose ATA^T satisfies the consecutive 11s property and is thus TU, this property may be lost when appending an all-ones row to A. Specifically, the matrix [mA] bmatrix1_m\\ A bmatrix obtained by adding a row of 11s of length m to A—does not, in general, have the consecutive 11s property in its transpose. There exists a small VI approval profile that yields a non-TU matrix; see Example (3), where a VI profile with 44 candidates and 33 voters together with the cardinality constraint (the first row) is not TU (its determinant is −2-2). [1111110010101001] bmatrix1&1&1&1\\ 1&1&0&0\\ 1&0&1&0\\ 1&0&0&1 bmatrix (3) Example (3) extends to Example (4) with 2m2m candidates and 2m−12m-1 voters for any m≥2m≥ 2, whose determinant is 2−2m≤−22-2m≤-2. Hence, these matrices are not TU either. [12m−1(2m−1)TI2m−1] bmatrix1&1_2m-1\\ (1_2m-1)^T&I_2m-1 bmatrix (4) However, there are more classes of integer programs that can be solved in polynomial time. In particular, if the coefficients of the constraint matrix are in −2,−1,0,1,2\-2,-1,0,1,2\ and the sum of absolute values is at most 22 for each column, then the problem is polynomial time solvable [SCH03]. Such matrices are called generalized matching matrices. Theorem 9 (Schrijver [SCH03]). ILPs with a generalized matching matrix can be solved in strongly polynomial time. These matrices correspond to problems called (generalized) matching problems, hence the name. The corresponding ILPs capture a variety of well-known problems in polynomial time such as minimum cost flow, minimum cost (b-)matching and certain graph factor problems [SCH03]. These structures even remain FPT time solvable parameterized by the number p of additional columns [L25]. However, we are facing the problem of having an additional row, which is shown to be, in general, not FPT assuming FPT is not equal to W[1] (a common hypothesis in parameterized complexity similar to P versus NP) [L25]. Fortunately, we can alter ILP-GT slightly and obtain a generalized matching matrix. Before we show the proof, note that if there is a candidate that is not approved by any voter, we can delete this candidate from the instance. If k is larger than the remaining candidates, we take all those remaining candidates and greedily fill up our committee with any candidate from the discarded list to obtain an optimal solution. If there is at least one candidate that is approved by only one voter, then we add a new dummy voter vdv_d that approves exactly all of candidates with only one approval. This voter vdv_d will have a zero contribution to the objective function. Hence, in the following, we assume w.l.o.g. that all candidates are approved by exactly two voters. Theorem 10. Generalized Thiele with ΔC=2 _C=2 can be solved in polynomial time. Proof. We modify the formulation of ILP-GT as follows. First, we replace Constraint (1) by the following equality: ∑v∈V∑i∈[k]xv,i=2k. _v∈ V _i∈[k]x_v,i=2k. (5) Second, we strengthen Constraint (2) by replacing the inequality with equality: ∑i∈[k]xv,i=∑c∈Avyc∀v∈V. _i∈[k]x_v,i= _c∈ A_vy_c \;∀ v∈ V. (6) Constraint (1) previously ensured that exactly k candidates are selected. As argued above, each candidate has exactly two supporters, so choosing any candidate (represented by variable ycy_c) implies that two variables xv,ix_v,i must be set to 11 (one for each approving voter) for valid solutions. Thus, replacing (1) by (5) and enforcing equality in Constraint (6) shifts the responsibility for enforcing the committee size from the ycy_c variables to the xv,ix_v,i variables. After these modifications, each variable xv,ix_v,i and ycy_c (each corresponding to one column of the constraint matrix) appears in exactly 2 constraints with coefficients in −1,1\-1,1\ (and 0 everywhere else). This implies that the resulting constraint matrix is a generalized matching matrix. By applying Theorem 9, we obtain a solution in polynomial time. ∎ 5.2 FPT Algorithm Parameterized by the Score Next, we prove that Generalized Thiele is FPT parameterized by k+ΔCk+ _C. The result relies on reducing the problem to a set cover variant called p-partial set cover that is solvable efficiently. In the p-partial set cover problem, we are given a universe U of t elements, and a set of subsets S of size s. The goal is to cover at least p different elements of U using the minimal number of sets in S. This problem is FPT time solvable parameterized by p. Theorem 11 (Bläser [BLÄ03]). A minimum p-partial set cover can be computed in time 2O(p)⋅s⋅t2^O(p)· s· t. Note that this algorithm also solves the weighted p-partial set cover problem where each set in S is assigned a weight and the goal is to find the minimum weight set cover hitting at least p distinct elements of U. Our algorithm reduces Generalized Thiele to p-partial set cover with p bounded by a function of k and ΔC _C. We view each voter as an element of the universe and every candidate as the set of supporters. Contrary to the set cover problem, in Generalized Thiele, it can be beneficial to “cover” a voter multiple times. To implement this in our reduction, we use color coding, a powerful tool to design FPT time algorithms (see, e.g., the book of Cygan et al. [CFK+15]). Color coding is used to color solution candidates such that, with high probability, an optimal solution only takes one solution candidate per color. We use the colors to color all approvals where each color indicates the additive contribution to the valuation function. This allows us to create different elements not just for every approval, but also the way it contributes to the objective function, e.g., the number of times a voter has been “covered”. To derandomize color coding, splitters have been introduced [NSS95]. Splitters compute a number of colorings instead of a single one such that at least one coloring has the desired property that an optimal solution only takes one solution candidate per color. This can be expressed in terms of hash functions: Definition 12. An (n,k,ℓ)(n,k, ) splitter is a family of hash functions F from 1,2,…,n\1,2,…,n\ to 1,2,…,ℓ\1,2,…, \ such that for every S⊆1,2,…,nS \1,2,…,n\ with |S|=k|S|=k, there exists a function f∈Ff∈ F that splits S evenly; that is, for every j,j′≤ℓj,j ≤ , we have |f−1(j)∩S||f^-1(j)∩ S| and |f−1(j′)∩S||f^-1(j )∩ S| differ by at most 1. Lemma 13 (Naor, Schulman, and Srinivasan [NSS95]). There exists an (n,k,k)(n,k,k) splitter of size ekkO(log(k))log(n)e^kk^O( (k)) (n) which is computable in time ekkO(log(k))⋅nlog(n)e^kk^O( (k))· n (n). Equipped with splitters, we can finally present the main result of this section. Theorem 14. Generalized Thiele is FPT parameterized by k+ΔCk+ _C. Proof. The main idea of this proof is to reduce Generalized Thiele to p-partial set cover such that p is bounded by k and ΔC _C. Observe that any k candidates can satisfy at most k⋅ΔCk· _C different voters. As the function is bounded by the parameter, we can guess the correct coverage. This already resembles the p-partial set cover problem where voters are elements, candidates are sets of voters that approve them. However, it does not capture that is adds to the objective function if we select two candidates that cover the same voters. We simulate this by using color coding to color all approvals. Each color indicates the additive contribution to the valuation function. This allows us create different elements not just for every approval, but also the way it contributes to the objective function. In particular, the additive contribution to the objective function is mimnicked by introducing different quantities of covered elements. Formally, we are given candidates C=c1,c2,…,cmC=\c_1,c_2,…,c_m\ and voters V=v1,v2,…,vnV=\v_1,v_2,…,v_n\. We visualize the approvals of voters to candidates as a matrix A∈0,1n×mA∈\0,1\^n× m. An entry ai,j=1a_i,j=1 if voter viv_i approves candidate cjc_j, otherwise ai,j=0a_i,j=0. Denote by q the number of 11s in the matrix. Observe that q≤m⋅ΔCq≤ m· _C. We color all 11s in the matrix with kΔCk _C colors 1,2,…,kΔC1,2,…,k _C. Each consecutive ΔC _C colors belong to the same type, e.g., colors 1+ΔC(i−1)1+ _C(i-1) to ΔC⋅i _C· i belong to class type i. Color class c states that the corresponding 11s contribute 1/c1/c to the objective function. As there are at most kΔCk _C approvals in any solution with k candidates, we can compute an (q,kΔ,kΔ)(q,k ,k ) splitter that contains are a coloring that colors all 11s of an optimal solution (see Lemma 13) differently. To guarantee the right meaning of the color, we further try all permutations of color classes for each coloring. Assume we are given a correct coloring, that is, an optimal solution is colored correctly. We use this coloring and the approval matrix A to compute a matrix A′∈0,12k!n×nA ∈\0,1\^2k!n× n that splits voters according to the color of their approvals. Each column a∗,ja_ ,j of A defines column a∗,j′a _ ,j of A′A : the entries 1+2k!(i−1)1+2k!(i-1) to 2k!(i)2k!(i) entries of a∗,j′a _ ,j belong to the iith entry of a∗,j′a _ ,j: If a∗,j′=0a _ ,j=0, all 2k!2k! entries are 0. Otherwise, if a∗,j′=1a _ ,j=1 and 11 is of color class c, then we put a 11 in all entries from 1+∑ℓ=2ck!/c1+ _ =2^ck!/c to ∑ℓ=2ck!/c+k!/c _ =2^ck!/c+k!/c, all other entries are 0. We can now describe the p-partial set cover instance. Every row in A′A corresponds to an element, hence U has size 2k!n2k!n. Every column a∗,j′a _ ,j corresponds to a set SjS_j, where a 11 in the corresponding row indicates that the element is in SjS_j. Hence, there are m many sets in S. Regarding q, we cover at least k many elements in any solution of size k (if there is a candidate that has zero approvals, we can delete it in a preprocessing step), and at most k⋅k!ΔCk· k! _C. Using binary search for the largest value within these bounds that does not use more than k elements in a solution, we directly get our optimal solution by taking the corresponding candidates. Correctness. If there exists an optimal solution of value OPT to Generalized Thiele, then there exists an optimal solution to the p-partial set cover instance of value OPT ⋅2k!· 2k!. Let COPT⊆C OPT C be the committee of an optimal solution. Assume that we are given a coloring (which we are given with high probability) such that all 11s in A are colored correctly, e.g., each row with ℓ approvals of the submatrix AOPTA OPT restricted to the columns corresponding to COPTC OPT uses each colorclass 1,2,…,k1,2,…,k exactly once. Then one can see that the set SOPTS OPT corresponding to COPTC OPT will give the desired solution. Now assume that we are given an optimal solution over all colorings of value OPT for p-partial cover that uses at most k sets SOPTS OPT. In the submatrix A′OPTA OPT restricted to the sets OPTS OPT of the optimal solution, each row must use each color 1,2,…,k1,2,…,k exactly once as otherwise there would be a better coloring achieving a higher value for any even for the same set. Now, this corresponds to the optimal solution COPTC OPT with value OPT/2k!/2k!. If there would be a better solution to Generalized Thiele, it would immediately imply a better solution to the p-partial set cover instance as outlined above, which is a contradiction. Running time. Coloring all 11s takes time O(mn)O(mn). Computing A′A takes time 2k!nm2k!nm. Computing the splitter takes time ekkO(log(k))qlog(q)e^kk^O( (k))q (q). Using Theorem 11, it takes time 2O(k⋅k!ΔC)⋅2k!n⋅m2^O(k· k! _C)· 2k!n· m for each of the ekkO(log(k))log(n)e^kk^O( (k)) (n) guesses and (ΔCk)k( _Ck)^k permutations of the color classes. This gives an overall running time of 2O(k4⋅k!ΔClog(k!ΔC))⋅n⋅m2.∎2^O(k^4· k! _C (k! _C))· n· m^2. This yields the following FPT algorithm. Proposition 15. For every Thiele sequence w, w-Thiele can be solved in time 2dO(d)⋅nmO(1)2^d^O(d)· nm^O(1), hence it is FPT parameterized by d, the total score of an optimal solution. Proof. In the case n<kn<k, we can find a committee that has at least one representative of every voter (e.g., by using a greedy algorithm). Since w1=1w_1=1, we have n≤dn≤ d. As w-Thiele is FPT with respect to n [FSS+18], in this case their algorithm is also FPT with respect to d with the running time at most O∗(22O(d))≤22O(d)⋅(dm)O(1)O^*(2^2^O(d))≤ 2^2^O(d)·(dm)^O(1). In the case n≥kn≥ k, using a greedy algorithm, we can find a committee that represents at least k voters (every taken candidate covers at least one additional voter or it already represents k voters). Since w1=1w_1=1, we have k≤dk≤ d. By taking candidate c to the committee with the highest |Vc||V_c|, it has to be ΔC≤d _C≤ d. Therefore, we have k+ΔC≤2dk+ _C≤ 2d and an FPT algorithm parameterized by k+ΔCk+ _C is an FPT algorithm parameterized by d. Hence, the application of Theorem˜14 provides an algorithm with the running time at most 2O(d5⋅d!log(d!d))⋅n⋅m2.2^O(d^5· d! (d!d))· n· m^2. The running time from both cases can be upper-bounded by 2dO(d)⋅n⋅mO(1)2^d^O(d)· n· m^O(1), which has only linear time dependency on n. This finishes the proof. ∎ As discussed in the Related Work section, a recent result by Gupta, Jain, Saha, Saurabh and Upasana [GJS+25] also provides an FPT algorithm parameterized by d. They solved Submodular Multiwinner Election with parameter t that is the number of approvals in a solution. Note that ΔC≤t≤ΔC⋅k _C≤ t≤ _C· k and that t can be as large as ΔC⋅k _C· k. Their results also use color-coding. In particular, they color all candidates with k colors, and all voters with t colors, i.e., every candidates of an optimal solution and all of the corresponding, at most t approvals in an optimal solution are colored with a different color. It remains to now greedily take the candidates from each color that indeed covers all approvals with the desired colors. Their running time is kt+1k!t!nO(1)⋅mO(1)k^kt^t+1k!t!n^O(1)· m^O(1) which for, e.g. for PAV, this yields 22(2t)2⋅t2t+1⋅nO(1)⋅mO(1)2^2(2t)^2· t^2t+1· n^O(1)· m^O(1). In comparison to our algorithm, our running time in terms of ΔC _C and n are better, in particular the dependency on ΔC _C is bounded by a factor of 2ΔClog(ΔC)2 _C ( _C) and our algorithm runs in time truly linear in n. We would also like to highlight that while both algorithms use color coding at its heart, the approaches differ significantly. While they color candidates and voters, we just color the approvals of each voter. This results in different amount, kind, and meaning of guesses and construction of the overall solution. 6 Conclusion and Future Work We presented new algorithms for computing optimal committees under Thiele rules. We identified structural properties of optimal solutions, which on Voter Interval instances enable a dynamic programming approach over a chain of subsets of candidates. We also resolved an open problem by showing that winner determination under any Thiele rule is polynomial-time solvable when each candidate is approved by at most two voters, using an ILP-based approach. Furthermore, we provided an FPT algorithm parameterized by k+ΔCk+ _C using color-coding technique, which we apply to obtain an FPT algorithm parameterized by the total score d. One question raised in the conference version of this paper [LS26] was whether winner determination under PAV on Voter Interval instances is polynomial-time solvable or NP-hard. This question has since been resolved by two independent groups, each of which obtained a polynomial-time algorithm [MS26, ALS+26]. Nevertheless, several directions remain open. In particular, it remains unknown whether the ILP-based result for ΔC=2 _C=2 can be replaced by a purely combinatorial algorithm—a question that also arises in the context of Thiele rules on Candidate Interval profiles [PET18]. It is natural to ask whether Theorem˜7 extends to more general preference domains such as Voter-Candidate Interval [DBW+25, EFI+24, GBS+21]. In contrast to [DBW+25], whose objective allows discarding dominated candidates, dominated candidates crucially affect Thiele scores. Finally, our structural results and algorithms could be used to reason about tied committees, for example by analyzing possible and necessary winners under Thiele rules, since our methods that compute optimal scores and can handle preselected candidates (by adjusting Thiele sequences in Generalized Thiele). Acknowledgements We thank Andrei Constantinescu and Piotr Faliszewski for discussions of our results that helped us clarify and improve their presentation. We also thank the anonymous reviewers for their valuable feedback. Alexandra Lassota was supported by the Dutch Research Council (NWO) under project number VI.Veni.242.293. Krzysztof Sornat was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 101002854). References [ALS+26] D. Avramidis, A. Lassota, U. Schmidt-Kraepelin, and A. Vetta (2026) Computing Thiele rules on interval elections and their generalizations. CoRR abs/2605.03067. Cited by: §6. [AGG+15] H. Aziz, S. Gaspers, J. Gudmundsson, S. Mackenzie, N. Mattei, and T. Walsh (2015) Computational aspects of multi-winner approval voting. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), p. 107–115. Cited by: §1.1, §1, §2, §4. [BFF21] S. Barman, O. Fawzi, and P. Fermé (2021) Tight approximation guarantees for concave coverage problems. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), p. 9:1–9:17. Cited by: §1.1. [BFG+22] S. Barman, O. Fawzi, S. Ghoshal, and E. Gürpinar (2022) Tight approximation bounds for maximum multi-coverage. Math. Program. 192 (1), p. 443–476. Cited by: §1.1, §2. [BSU13] N. Betzler, A. Slinko, and J. Uhlmann (2013) On the computation of fully proportional representation. J. Artif. Intell. Res. 47, p. 475–519. Cited by: §1.1, §1. [BLÄ03] M. Bläser (2003) Computing small partial coverings. Inf. Process. Lett. 85 (6), p. 327–331. Cited by: Theorem 11. [BBC+24] N. Boehmer, M. Brill, A. Cevallos, J. Gehrlein, L. S. Fernández, and U. Schmidt-Kraepelin (2024) Approval-based committee voting in practice: A case study of (over-)representation in the polkadot blockchain. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), p. 9519–9527. Cited by: §1. [BFK+20a] R. Bredereck, P. Faliszewski, A. Kaczmarczyk, D. Knop, and R. Niedermeier (2020) Parameterized algorithms for finding a collective set of items. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), p. 1838–1845. Cited by: §1.1. [BFN+15] R. Bredereck, P. Faliszewski, R. Niedermeier, P. Skowron, and N. Talmon (2015) Elections with few candidates: Prices, weights, and covering problems. In Proceedings of the 4th Conference on Algorithmic Decision Theory (ADT 2015), p. 414–431. Cited by: §1.1. [BFN+20b] R. Bredereck, P. Faliszewski, R. Niedermeier, P. Skowron, and N. Talmon (2020) Mixed integer programming with convex/concave constraints: Fixed-parameter tractability and applications to multicovering and voting. Theor. Comput. Sci. 814, p. 86–105. Cited by: §1.1. [BP23] M. Brill and J. Peters (2023) Robust and verifiable proportionality axioms for multiwinner voting. In Proceedings of the 24th ACM Conference on Economics and Computation (EC 2023), p. 301. Cited by: §1. [BSS18] J. Byrka, P. Skowron, and K. Sornat (2018) Proportional approval voting, harmonic k-median, and negative association. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), p. 26:1–26:14. Cited by: §1.1. [C83] J. R. Chamberlin and P. N. Courant (1983-09) Representative deliberations and representative decisions: Proportional representation and the Borda rule. Am. Political Sci. Rev. 77, p. 718–733. Cited by: §1. [CE21] A. C. Constantinescu and E. Elkind (2021) Proportional representation under single-crossing preferences revisited. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), p. 5286–5293. Cited by: §1.1. [CFK+15] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh (2015) Parameterized algorithms. Springer. Cited by: §2, §5.2. [DBW+25] C. Dong, M. Bullinger, T. Wąs, L. Birnbaum, and E. Elkind (2025) Selecting interlacing committees. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), p. 630–638. Cited by: §3, §6. [DMM+20] S. Dudycz, P. Manurangsi, J. Marcinkowski, and K. Sornat (2020) Tight approximation for proportional approval voting. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), p. 276–282. Cited by: §1.1, §2. [EFI+24] E. Elkind, P. Faliszewski, A. Igarashi, P. Manurangsi, U. Schmidt-Kraepelin, and W. Suksompong (2024) The price of justified representation. ACM Trans. Economics and Comput. 12 (3), p. 11:1–11:27. Cited by: §6. [ELP17] E. Elkind, M. Lackner, and D. Peters (2017) Structured preferences. In Trends in Computational Social Choice, U. Endriss (Ed.), p. 187–207. Cited by: §1, §1.1, §1, §1, §1. [ELP25] E. Elkind, M. Lackner, and D. Peters (2025) Preference restrictions in computational social choice: A survey. CoRR abs/2205.09092v2. Cited by: §1, §1.1, §1, §1, §1. [EL15] E. Elkind and M. Lackner (2015) Structure in dichotomous preferences. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), p. 2019–2025. Cited by: §2. [FHH+11] P. Faliszewski, E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe (2011) The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Inf. Comput. 209 (2), p. 89–107. Cited by: §2. [FSS+18] P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon (2018) Multiwinner analogues of the plurality rule: Axiomatic and algorithmic perspectives. Soc. Choice Welf. 51 (3), p. 513–550. Cited by: §1.1, §5.2, footnote 2. [GBS+21] M. T. Godziszewski, P. Batko, P. Skowron, and P. Faliszewski (2021) An analysis of approval-based committee rules for 2D-Euclidean elections. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), p. 5448–5455. Cited by: §1, §6. [GJS+25] S. Gupta, P. Jain, S. Saha, S. Saurabh, and A. Upasana (2025) More efforts towards fixed-parameter approximability of multiwinner rules. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025), p. 3891–3899. Cited by: §1.1, §5.2. [JST20] P. Jain, K. Sornat, and N. Talmon (2020) Participatory budgeting with project interactions. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), p. 386–392. Cited by: §1.1, §1.1. [LS21] M. Lackner and P. Skowron (2021) Consistent approval-based multi-winner rules. J. Econ. Theory 192, p. 105173. Cited by: §1. [LS23] M. Lackner and P. Skowron (2023) Multi-winner voting with approval preferences. Springer. Cited by: §1, §1, §1. [L25] A. Lassota and K. Ligthart (2025) Parameterized algorithms for matching integer programs with additional rows and columns. In Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), p. 112:1–112:18. Cited by: §5.1. [LS26] A. Lassota and K. Sornat (2026) Algorithms for structured elections under Thiele voting rules. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI 2026), p. 17084–17092. Cited by: §6, footnote 1. [LG16] H. Liu and J. Guo (2016) Parameterized complexity of winner determination in minimax committee elections. In Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), p. 341–349. Cited by: §1. [MS26] P. Manurangsi and K. Sornat (2026) Polynomial-time algorithm for Thiele voting rules with voter interval preferences. CoRR abs/2604.05953. Cited by: §6. [NSS95] M. Naor, L. J. Schulman, and A. Srinivasan (1995) Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS 1995), p. 182–191. Cited by: §5.2, Lemma 13. [PL20] D. Peters and M. Lackner (2020) Preferences single-peaked on a circle. J. Artif. Intell. Res. 68, p. 463–502. Cited by: §1. [PET18] D. Peters (2018) Single-peakedness and total unimodularity: New polynomial-time algorithms for multi-winner elections. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), p. 1169–1176. Cited by: §1, §1, §1, §5.1, §5.1, §6. [SCH03] A. Schrijver (2003) Combinatorial optimization: Polyhedra and efficiency. Algorithms and Combinatorics, Vol. 24, Springer. Cited by: §5.1, §5.1, Theorem 9. [SFL16] P. Skowron, P. Faliszewski, and J. Lang (2016) Finding a collective set of items: From proportional multirepresentation to group recommendation. Artif. Intell. 241, p. 191–216. Cited by: §1.1, §1, §2, §4. [SVX22] K. Sornat, V. Vassilevska Williams, and Y. Xu (2022) Near-tight algorithms for the Chamberlin-Courant and Thiele voting rules. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022), p. 482–488. Cited by: §1.1, §1.1, §1.1, §1.1, §2, §5.1. [THI95] T. Thiele (1895) Om flerfoldsvalg. In Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger (in Danish), p. 415–441. Cited by: §1, §2. [YW18] Y. Yang and J. Wang (2018) Parameterized complexity of multi-winner determination: More effort towards fixed-parameter tractability. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018), p. 2142–2144. Cited by: §1, §5. [YW23] Y. Yang and J. Wang (2023) Parameterized complexity of multiwinner determination: More effort towards fixed-parameter tractability. Auton. Agents Multi Agent Syst. 37 (2), p. 28. Cited by: §1, §1.1, §1.1, §5.