pith. sign in

arxiv: 2604.11933 · v1 · submitted 2026-04-13 · 💻 cs.GT

Navigating the Complexity Landscape of Nominee Selection in Schulze Voting

Katar\'ina Cechl\'arov\'a , J\"org Rothe , \v{S}imon Schierreich , Ildik\'o Schlotter This is my paper

Pith reviewed 2026-05-10 14:51 UTC · model grok-4.3

classification 💻 cs.GT
keywords Schulze votingPossible PresidentNecessary Presidentparameterized complexityNP-completenessvoting theorycomputational social choice
0
0 comments X

The pith

Schulze nominee problems split into tractable and intractable cases by whether voter numbers are fixed or arbitrary.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper analyzes two questions about party nominations in Schulze elections: whether a distinguished party can pick a nominee who wins after all parties choose their candidates, and whether its nominee wins no matter what the others pick. It maps the exact computational cost of answering these questions when the number of voters, the largest party size, and the total number of parties are each treated as fixed constants, as bounded parameters, or as unbounded. The central contribution is a pair of sharp dichotomies that tie the difficulty of both problems directly to the number of voters. Readers should care because Schulze voting is already used in real elections and these results tell practitioners exactly when nomination decisions can be computed efficiently and when they become infeasible.

Core claim

We determine the parameterized complexity of the Possible President and Necessary President problems for Schulze voting with respect to all combinations of the three parameters: number of voters, maximum party size, and number of parties, each considered constant, a parameter, or unbounded. In particular we obtain dichotomies regarding the number of voters for both problems.

What carries the argument

The Possible President problem (does there exist a nomination choice for all parties such that the distinguished party's nominee is a Schulze winner) and the Necessary President problem (is the distinguished nominee a Schulze winner for every possible nomination by the other parties), classified by treating voter count, party size, and party count as constant/parameter/unbounded.

If this is right

  • When the number of voters is a fixed constant, both problems admit polynomial-time algorithms irrespective of party sizes and numbers.
  • Treating the number of voters as a parameter yields FPT algorithms or W[1]-hardness depending on the status of the other two parameters.
  • With an unbounded number of voters the Possible President problem is NP-complete and the Necessary President problem is coNP-complete, matching the earlier results.
  • The classification covers every combination of the three parameters, producing a complete map of tractability thresholds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Election organizers could use small voter counts as a practical criterion for when to compute nomination strategies exactly rather than heuristically.
  • The same parameter-based split might be worth checking for other Condorcet-consistent rules that share Schulze's path-strength definition.
  • If real-world electorates are small, the tractable cases identified here could be implemented directly in nomination software.

Load-bearing premise

The analysis assumes the standard model in which each party nominates exactly one candidate and every voter supplies a complete ranking over all candidates.

What would settle it

A polynomial-time algorithm for Possible President when the number of voters is unbounded, or an NP-hardness proof for the same problem when the number of voters is fixed to a small constant, would refute the claimed dichotomy.

Figures

Figures reproduced from arXiv: 2604.11933 by Ildik\'o Schlotter, J\"org Rothe, Katar\'ina Cechl\'arov\'a, \v{S}imon Schierreich.

Figure 1
Figure 1. Figure 1: q1 q2 q q3 ′ 2 q ′′ 2 v1 : q3 q1 q2 q ′ 2 q ′′ 2 v2 : q1 q2 q ′ 2 q ′′ 2 q3 v3 : q2 q ′ 2 q ′′ 2 q3 q1 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
read the original abstract

We study the Possible President problem and the Necessary President problem for Schulze voting, a rule that, due to its many desirable axiomatic properties, is popular in practice. In both problems, we are given an election with the candidates partitioned into a set of parties, and we are interested in questions about a given distinguished party. In the Possible President problem, we ask whether it is possible for the parties to each nominate exactly one candidate such that the nominee of the distinguished party is a Schulze winner of the resulting election with only the nominees running. In the Necessary President problem, we ask whether the distinguished party's nominee is a Schulze winner of the resulting election, irrespective of the nomination from the other parties. Rothe and Woitaschik have shown that Possible President is NP-complete and Necessary President is coNP-complete for Schulze elections. We complement and improve their results by a more fine-grained analysis: we determine the parameterized complexity of both problems with respect to all possible parameterizations, where we consider each of three natural parameters -- the number of voters, the maximum party size, and the number of parties -- to be either a constant, a parameter, or unbounded. In particular, we obtain dichotomies regarding the number of voters for both problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies the Possible President and Necessary President problems for Schulze voting. Candidates are partitioned into parties, each nominating exactly one candidate. Possible President asks whether there exists a nomination making the distinguished party's nominee a Schulze winner; Necessary President asks whether the distinguished party's nominee is a Schulze winner for every possible nomination by the other parties. Building on the NP-completeness of Possible President and coNP-completeness of Necessary President shown by Rothe and Woitaschik, the authors give a parameterized complexity classification for all combinations of three parameters (number of voters, maximum party size, number of parties) treated as constant, parameter, or unbounded, with explicit dichotomies obtained for the number-of-voters axis.

Significance. If the results hold, the paper supplies a complete fine-grained complexity map that sharpens the existing hardness results. The voter-number dichotomies cleanly separate polynomial-time, FPT, and hard regimes, which is useful for both theoretical understanding of Schulze voting and for practical multi-party nomination scenarios. The work also inherits and extends the standard election model (complete rankings, one nominee per party) used in prior proofs.

minor comments (2)
  1. [Abstract] Abstract: the claim that dichotomies are obtained for the number of voters is stated but not illustrated; a single-sentence summary of the tractable vs. hard cases would improve readability without lengthening the abstract.
  2. The manuscript would benefit from a summary table (perhaps in the introduction or conclusion) listing the complexity status for each of the 27 parameter combinations; this would make the overall landscape immediately visible to readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. The referee's summary accurately captures our parameterized complexity analysis of the Possible President and Necessary President problems for Schulze voting, including the dichotomies with respect to the number of voters. We appreciate the recognition that this provides a fine-grained complexity map building on prior NP- and coNP-completeness results.

Circularity Check

0 steps flagged

No significant circularity; results are self-contained complexity classifications

full rationale

The paper establishes parameterized complexity dichotomies for Possible President and Necessary President under Schulze voting by building directly on external NP- and coNP-completeness baselines from prior independent work (Rothe and Woitaschik). All load-bearing steps consist of explicit reductions, FPT algorithms, and case analyses with respect to the three parameters (voters, party size, number of parties), none of which reduce by construction to fitted values, self-definitions, or unverified self-citations. The cited hardness results function as independent starting points rather than being re-derived or assumed within the present manuscript, and the new fine-grained results (especially the voter-number dichotomies) are obtained via standard parameterized complexity techniques without circular dependence on the paper's own claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard results from parameterized complexity theory and the correctness of the cited NP/coNP-completeness proofs; no free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (1)
  • standard math Standard assumptions of complexity theory (P ≠ NP, FPT ≠ W[1], etc.)
    Implicitly used when classifying problems as NP-complete, coNP-complete, or FPT versus para-NP-hard.

pith-pipeline@v0.9.0 · 5545 in / 1206 out tokens · 44259 ms · 2026-05-10T14:51:24.214615+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    Bartholdi III, Craig A

    2 John J. Bartholdi III, Craig A. Tovey, and Michael A. Trick. The computational difficulty of manipulating an election.Social Choice and Welfare, 6(3):227–241, 1989.doi:10.1007/ BF00295861. 3 John J. Bartholdi III, Craig A. Tovey, and Michael A. Trick. How hard is it to control an election?Mathematical and Computer Modelling, 16(8–9):27–40, 1992.doi:10.1...

    work page doi:10.1007/978-3-031-60099-9_4 1989

  2. [2]

    6 Markus Brill and Felix Fischer

    URL:https://eccc.weizmann.ac.il/eccc-reports/2003/TR03-049/index.html. 6 Markus Brill and Felix Fischer. The price of neutrality for the ranked pairs method. In Jörg Hoffmann and Bart Selman, editors,Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI ’12, pages 1299–1305. AAAI Press, 2012.doi:10.1609/aaai.v26i1.8250. 7 KatarínaCechlá...

    work page doi:10.1609/aaai.v26i1.8250 2003

  3. [3]

    10 Vincent Conitzer, Tuomas Sandholm, and Jérôme Lang

    URL:http://ijcai.org/Proceedings/09/Papers/029.pdf. 10 Vincent Conitzer, Tuomas Sandholm, and Jérôme Lang. When are elections with few candidates hard to manipulate?Journal of the ACM, 54(3), 2007.doi:10.1145/1236457.1236461. 11 Vincent Conitzer and Toby Walsh. Barriers to manipulation in voting. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lan...

    work page doi:10.1145/1236457.1236461 2007

  4. [4]

    In: Handbook of Computational Social Choice, Cambridge University Press, pp

    doi:10.1017/CBO9781107446984.007. 12 Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, Cham, August 2015.doi:10.1007/978-3-319-21275-3. 13 Michelle Döring, Markus Brill, and Jobst Heitzig. The River voting method. In Sven Koenig, Chad Jenki...

    work page doi:10.1017/cbo9781107446984.007 2015

  5. [5]

    Learning How to V ote with Principles: Axiomatic Insights Into the Collective Decisions of Neural Networks.J

    URL:http://www.ijcai.org/Abstract/16/044. 15 Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. How hard is bribery in elections?Journal of Artificial Intelligence Research, 35:485–532, 2009.doi:10.1613/jair

    work page doi:10.1613/jair 2009

  6. [6]

    Hemaspaandra, and Jörg Rothe

    16 Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. Llull and Copeland voting computationally resist bribery and constructive control.Journal of Artificial Intelligence Research, 35:275–341, 2009.doi:10.1613/jair.2697. 17 Piotr Faliszewski, Stanisław Kaźmierowski, Grzegorz Lisowski, Ildikó Schlotter, and Paolo Turrini. Computin...

    work page doi:10.1613/jair.2697 2009

  7. [7]

    19 Michael R

    doi:10.1017/CBO9781107446984.008. 19 Michael R. Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems.Theoretical Computer Science, 410(1):53–61, 2009.doi:10.1016/j.tcs.2008.09.065. K. Cechlárová, J. Rothe, Š. Schierreich, and I. Schlotter 27 20 Michael R. Garey and David S. J...

    work page doi:10.1017/cbo9781107446984.008 2009

  8. [8]

    Hemaspaandra, and Jörg Rothe

    21 Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. Anyone but him: The complexity of precluding an alternative.Artificial Intelligence, 171(5–6):255–285, 2007.doi: 10.1016/j.artint.2007.01.005. 22 Wesley H. Holliday and Eric Pacuit. Split cycle: A new Condorcet-consistent voting method independent of clones and immune to spoilers.Public Choice, ...

    work page doi:10.1016/j.artint.2007.01.005 2007

  9. [9]

    On the parameterized complexity of party nominations

    25 Neeldhara Misra. On the parameterized complexity of party nominations. In Saša Pekeč and Kristen Brent Venable, editors,Proceedings of the 6th International Conference on Algorithmic Decision Theory, ADT ’19, volume 11834 ofLecture Notes in Computer Science, pages 112–125. Springer, 2019.doi:10.1007/978-3-030-31489-7_8. 26 David Parkes and Lirong Xia. ...

    work page doi:10.1007/978-3-030-31489-7_8 2019

  10. [10]

    27 Krzysztof Pietrzak

    doi:10.1609/aaai.v26i1.8258. 27 Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems.Journal of Computer and System Sciences, 67(4):757–771, 2003.doi:10.1016/s0022-0000(03)00078-3. 28 Jörg Rothe.Complexity Theory and Cryptology: An Introduction to Cryptocomplexity. ...

    work page doi:10.1609/aaai.v26i1.8258 2003

  11. [11]

    29 Jörg Rothe and Jana Woitaschik

    doi:10.1007/3-540-28520-2. 29 Jörg Rothe and Jana Woitaschik. Complexity of the possible and necessary president problem in Schulze voting. In Lucia Moura and Conrado Martínez, editors,Proceedings of the 17th Latin American Theoretical Informatics Symposium, LATIN ’26, Lecture Notes in Computer Science. Springer,

    work page doi:10.1007/3-540-28520-2

  12. [12]

    31 Ildikó Schlotter, Katarína Cechlárová, and Diana Trellová

    URL:https://dl.acm.org/doi/10.5555/ 3709347.3743822. 31 Ildikó Schlotter, Katarína Cechlárová, and Diana Trellová. Parameterized complexity of candidate nomination for elections based on positional scoring rules.Journal of Autonomous Agents and Multi-Agent Systems, 38(2), 2024.doi:10.1007/s10458-024-09658-5. 32 Markus Schulze. A new monotonic, clone-indep...

    work page doi:10.1007/s10458-024-09658-5 2024

  13. [13]

    33 Krzysztof Sornat, Virginia Vassilevska Williams, and Yinzhan Xu

    doi:10.1007/s00355-010-0475-4. 33 Krzysztof Sornat, Virginia Vassilevska Williams, and Yinzhan Xu. Fine-grained complexity and algorithms for the Schulze voting method. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors,Proceedings of the 22nd ACM Conference on Economics and Computation, EC ’21, pages 841–859. ACM, 2021.doi:10.1145/3465456.3467...

    work page doi:10.1007/s00355-010-0475-4 2021