Nearly Group-Separable Elections

Piotr Faliszewski; Jan Jabrocki; Stanisław Kaźmierowski; Kristýna Pekárková; Šimon Schierreich; Ildikó Schlotter

cs.GTSep 27, 2026

Nearly Group-Separable Elections

Authors: Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski, Kristýna Pekárková, Šimon Schierreich, Ildikó Schlotter

Organizations: AGH University of Krakow, Poland · University of Warsaw, Poland · Charles University, Czechia · Czech Technical University in Prague, Czechia · ELTE Centre for Economic and Regional Studies, Hungary · Budapest University of Technology and Economics, Hungary

Abstract

We study the problem of computing how close a given election is to being group-separable, measuring proximity by swaps of adjacent candidates in the votes. We also consider several other domains, including caterpillar group-separable, balanced group-separable, single-peaked, and single-crossing ones. Our problem is generally intractable, but we find practical FPT algorithms parameterized by the number of candidates or swaps. For the latter case, our algorithm applies to all domains characterized by finite forbidden subelections, resolving a well-established open problem. We supplement our theoretical findings with experimental analysis.

Figures & tables

	—	$n$	$m$	$d$
$\mathrm{GS}$	?	?	$\mathcal{O}^{*}(3^{m})$ [T 4.3 ]	$\mathcal{O}^{*}(6^{d})$ [C 4.8 ]
$\mathrm{GS}\text{/}\allowbreak\mathrm{cat}$	${\mathrm{NP}}$ -c [T 3.1 ]	para- ${\mathrm{NP}}$ -c [T 3.1 ]	$\mathcal{O}^{*}(2^{m})$ [T 4.4 ]	$\mathcal{O}^{*}(8^{d})$ [C 4.8 ]
$\mathrm{GS}\text{/}\allowbreak\mathrm{bal}$	${\mathrm{NP}}$ -c [T 3.2 ]	?	$\mathcal{O}^{*}((2\sqrt{2})^{m})$ [T 4.4 ]	$\mathcal{O}^{*}(2^{2d^{2}})$ [T 4.9 ]
$\mathrm{Identity}$	${\mathrm{NP}}$ -c [BTT]	para- ${\mathrm{NP}}$ -c [DKNS]	$\mathcal{O}^{*}(2^{m})$ [BFGNR]	$\mathcal{O}^{*}(1.53^{d})$ [BFGNR]
$\mathrm{Antagonism}$	${\mathrm{NP}}$ -c [T 3.6 ]	para- ${\mathrm{NP}}$ -c [T 3.6 ]	$\mathcal{O}^{*}(2^{\mathcal{O}\mathopen{}\left(m\log m\right)})$ [T 4.2 ]	$\mathcal{O}^{*}(3.06^{d})$ [T 4.10 ]
$\mathrm{Separation}$	${\mathrm{NP}}$ -c [T 3.4 ]	$\mathcal{O}^{*}(2^{n})$ [T 3.3 ]	$\mathcal{O}^{*}(2^{m})$ [T 4.4 ]	$\mathcal{O}^{*}(5^{d})$ [T 4.10 ]

Table 1: An overview of our complexity and algorithmic results. Citations for known results are abbreviated as follows: BFGNR refers to ( Betzler et al. 2009 ) , BTT to ( Bartholdi III, Tovey, and Trick 1989 ) , DKNS to ( Dwork et al. 2001 ) , ELP to ( Erdélyi, Lackner, and Pfandler 2017 ) , and LPE to ( Lakhani, Peters, and Elkind 2019 ) .

Panel of Figure 1 — Figure 1: Results of our numerical experiments.

Figure 2: Probability of retaining winners (being successful) for

\mathrm{GS}\text{/}\allowbreak\mathrm{cat}

\mathrm{GS}\text{/}\allowbreak\mathrm{bal}

\mathrm{GS}

, and

\mathrm{Single}\text{-\allowbreak}\mathrm{Peaked}

projections.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Illustration for the proof of Theorem 3.2 . The figure depicts the prefect binary tree $T_{8n}$ . The candidate set displayed in the rectangle at the bottom of a given subtree contains those candidates that are mapped by $\varphi^{\star}$ to the leaves of the given subtree, with the size of this set written underneath.

Figure 4: Running time of our algorithms on 1000 elections sampled from the SP/Conitzer culture.

Figure 5: Running time of our algorithms on 1000 elections sampled from the SP/Walsh culture.

Figure 6: Running time of our algorithms on 1000 elections sampled from the Single-Crossing culture.

Figure 7: Running time of our algorithms on 1000 elections sampled from the GS/cat culture.

Figure 8: Running time of our algorithms on 1000 elections sampled from the GS/bal culture.

Figure 9: Running time of our algorithms on 1000 elections sampled from the Impartial culture.

Figure 10: Running time of our algorithms on 1000 elections sampled from the URN-0.2 culture.

Figure 11: Running time of our algorithms on 1000 elections sampled from the URN-0.5 culture.

Figure 12: Running time of our algorithms on 1000 elections sampled from the EUC/uni culture.

Absolute distance
	GS/cat					GS/bal					GS
Culture	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share
NM-0.1	108.6 $\pm$ 4.7	109	99	115	0	80.3 $\pm$ 6.5	79.5	69	91	20	76.6 $\pm$ 4.9	75.5	69	85	80
NM-0.3	270.1 $\pm$ 14.0	274.5	245	284	0	270.2 $\pm$ 20.3	273	247	312	0	247.3 $\pm$ 18.2	248	218	275	100
NM-0.5	383.5 $\pm$ 21.4	384	358	415	80	448.5 $\pm$ 31.7	448	401	492	0	383.1 $\pm$ 21.4	382.5	358	415	20
NM-0.7	448.9 $\pm$ 16.6	447.5	421	475	100	578.3 $\pm$ 14.6	580	560	604	0	448.9 $\pm$ 16.6	447.5	421	475	0

Appendix

Table 2: Swap distance to the closest election of each group-separable domain for the elections of the map experiment (

8

candidates,

96

voters,

10

elections per culture). The top panel reports absolute distances, the bottom panel the same statistics normalized per voter (i.e., divided by

n=96

). The share column gives the percentage of elections for which the domain is the closest of the three (ties split evenly; the general group-separable domain is only credited when strictly closer than both special cases). In every row the domain with the largest share is set in bold; cells are shaded proportionally to their value relative to the maximum of their statistic over all cells (shares relative to

100\%

Absolute distance
	GS/cat					GS/bal					GS					SPeak
Culture	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share
NM-0.1	101.2 $\pm$ 9.4	101	66	133	0	75.0 $\pm$ 9.9	75	44	112	0	70.9 $\pm$ 8.4	71	44	97	0	31.5 $\pm$ 6.7	31	13	55	100
NM-0.3	268.6 $\pm$ 15.1	268	222	313	0	260.2 $\pm$ 20.2	260	195	324	0	239.3 $\pm$ 17.1	239	190	293	0	179.6 $\pm$ 17.0	180	129	233	100
NM-0.5	383.2 $\pm$ 15.7	384	334	422	5.4	443.7 $\pm$ 24.7	443	354	519	0	381.7 $\pm$ 16.2	382	334	422	0.3	352.5 $\pm$ 22.9	352	272	436	94.3
NM-0.7	447.0 $\pm$ 12.3	448	401	481	99.3	582.3 $\pm$ 20.1	583	502	641	0	447.0 $\pm$ 12.3	448	398	481	0.6	513.5 $\pm$ 23.4	514	439	591	0.1

Appendix

Table 3: Swap distance to the closest election of each restricted domain (

8

candidates,

96

voters,

1000

elections per culture). The top panel reports absolute distances, the bottom panel the same statistics normalized per voter (i.e., divided by

n=96

). The share column gives the percentage of elections for which the domain is the closest of the four (ties split evenly; the general group-separable domain is only credited when strictly closer than both special cases). In every row the domain with the largest share is set in bold; cells are shaded proportionally to their value relative to the maximum of their statistic over all cells (shares relative to

100\%

Figure 13: The overall fraction of elections where

\mathrm{GS}\text{/}\allowbreak\mathrm{cat}

\mathrm{GS}\text{/}\allowbreak\mathrm{bal}

\mathrm{GS}

, or

\mathrm{Single}\text{-\allowbreak}\mathrm{Peaked}

is the closest structured domain.

Figure 14: An overview of closest domains per dataset and category.

Figure 15: An overview of closest domains per the number of candidates within an election.

Figure 16: Probability of retaining original winners (success rate) under the STV voting rule for

\mathrm{GS}\text{/}\allowbreak\mathrm{cat}

\mathrm{GS}\text{/}\allowbreak\mathrm{bal}

\mathrm{GS}

, and

\mathrm{Single}\text{-\allowbreak}\mathrm{Peaked}

projections.

Explore similar work

Algorithms for Structured Elections under Thiele Voting Rules
Jul 30, 2026Alexandra Lassota, Krzysztof SornatElections Majority Voting
TU Eindhoven, the Netherlands · AGH University, Poland
Query-efficient winner prediction in district-based elections
Sep 30, 2026Koustav De, Debajyoti Kar, Swagato SanyalElections Majority Voting
Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, India · Department of Computer Science and Automation, Indian Institute of Science Bengaluru, India · School of Computer Science, University of Sheffield, United Kingdom
Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections
Apr 21, 2026Itai Zilberstein, Ratip Emin Berker, George Li +1Elections Majority Voting
Carnegie Mellon University Pittsburgh, USA

Jul 30, 2026, cs.GTJ/K move · Enter open · S save

Algorithms for Structured Elections under Thiele Voting Rules

Alexandra Lassota, Krzysztof Sornat

TU Eindhoven, the Netherlands · AGH University, Poland

Elections Majority Voting

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Algorithms for Structured Elections under Thiele Voting Rules

Query-efficient winner prediction in district-based elections

Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections