Skip to content

Faster Verification of PJR+ via Mincuts

Sep 2026 · arXiv.org · Vol abs/2609.20579 · 0 citations · 24 references
Computer Science

TL;DR

It is demonstrated how to compute the largest value of $\alpha$ for which a committee still fails the axiom using this mincut formulation, and a direct mincut formulation of the problem on a bipartite graph is given.

Abstract

PJR$^+$ is a polynomial-time verifiable proportionality axiom for approval-based committee elections, but its known polynomial-time verification procedure relies on general submodular-function minimisation. We show that its objective is a maximum-closure problem and give a direct mincut formulation of the problem on a bipartite graph. Using an almost-linear-time maximum-flow algorithm, this yields an $\mathcal{O}(m(nk)^{1+o(1)})$-time verifier, where $n$, $m$, and $k$ are the numbers of voters, candidates, and committee members, respectively. The dependence of this bound on each parameter separately is almost linear: it is linear in $m$, and almost linear in $n$ and $k$. The verifier also returns an explicit group witnessing a violation and admits a slower but immediately implementable variant based on the preflow--push mincut algorithm. Finally, for the parameterised axiom $\alpha$-PJR$^+$, where $\alpha$ is used as a multiplier in the group size, we demonstrate how to compute the largest value of $\alpha$ for which a committee still fails the axiom using this mincut formulation.

View source

Similar papers

Preprint Sep 2026

Sub-polynomial parameterized complexity of $k$-core

Alternative parameterizations of the k-core problem are investigated to identify conditions under which it can be placed into sub-polynomial complexity classes, and the boundary of parallel tractability for the k-core problem is explored.

Y. S. To, Cristina G. Fernandes · 0 citations
Preprint Oct 2026

A Faster Auction Algorithm for Weighted Matroid Intersection

This is the first deterministic $(1-\varepsilon)$-approximation algorithm for the weighted matroid intersection problem whose query complexity is nearly linear in $n$ and polynomial in $1/\varepsilon$.

Tatsuya Terao · 1 citation
Sep 2026

Efficient Algorithms for Subdeterminant Maximization under Partition Matroids

We consider the determinant maximization problem under partition constraints: Given an $n\times n$ PSD matrix A and a partition matroid $M$ on $[n]$, find a base $S$ of $M$ that maximizes $\det(A_{S,S})$. We give an $e^{O(k)}$-approximation algorithm to find such a set $S$, where $k$ is the rank of $M$. This improves u...

Nikhil Bansal, Yu-Ze Xu · 0 citations
Sep 2026

Consequences of Polylogarithmic Membership Comparability for SAT

This expanded version of this paper develops the full weak-advantage regime, where saving $2^{-O((log n)^d)}$ gives randomized SAT exponent $d$ and PH exponent $d^k$ at fixed level $k$; the quasipolynomial and exponential hierarchy consequences; binary-comparator advice bounds; and the certificate-length boundary betwe...

Sebastian Ben Daniel · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.