d4-conf-aaai-2026-2989 (d4-conf-aaai-2026-2989)

Given a finite connected unweighted graph \(G=(P,E)\), rational masses \(\mu_p\ge 0\) summing to \(1\), and \(S\subseteq P\), decide whether every candidate set \(C\subseteq P\) with \(C\cap S\ne\varnothing\) has all possible IRV winners in \(S\). In each round, each location type \(p\) sends its mass \(\mu_p\) equally among its nearest remaining candidates, and any candidate tied for the fewest votes may be eliminated.

Given an explicitly represented finite connected simple undirected unweighted graph \(G=(P,E)\), put \(m=|P|\), and let \(d_G\) be shortest-path distance. The input includes a nonempty set \(S\subseteq P\).
A society is given by its support: a list of \(\tau\) distinct location types with positive binary rational masses summing to \(1\). Unlisted vertices have mass \(0\); \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Candidates may occupy any vertices, including vertices of zero mass, with at most one candidate per vertex. For a remaining candidate set \(R\), each type \(p\) divides its mass equally among all candidates minimizing \(d_G(p,c)\) over \(c\in R\).
Split-IRV recomputes these shares each round, eliminates one candidate of minimum share (any tied candidate may be chosen), and continues until one winner remains.
Call \(S\) an exclusion zone if every candidate set \(C\subseteq P\) with \(C\cap S\ne\varnothing\) has every possible Split-IRV winner in \(S\).

Is deciding whether \(S\) is an exclusion zone in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?

With one equal-weight voter at every vertex and the same splitting and elimination conventions, exclusion-zone verification is \(\mathrm{coNP}\)-complete. [Tomlinson, Ugander, and Kleinberg](https://ojs.aaai.org/index.php/AAAI/article/download/38775/42737).
For unit voters on trees, verification is polynomial-time under deterministic preference and elimination tie-breaking, a different convention. [Birmpas et al.](https://arxiv.org/html/2603.10290v3). No separate classification for the exact rational-mass problem above was located.

Result

The problem is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. Consequently, it is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, and belongs to \(\mathrm{P}\) if and only if \(\mathrm{P}=\mathrm{NP}\).

The hardness already holds when \(\tau=m\) and every listed mass is \(1/m\). Thus the support representation permits the known hard instances.

1. Transferring the uniform-voter hardness

Let \(\mathcal U\) denote exclusion-zone verification with one unit voter at every vertex, and let \(\mathcal Q\) denote the rational-mass problem in the question.

Tomlinson, Ugander, and Kleinberg prove that \(\mathcal U\) is \(\mathrm{coNP}\)-complete. Their graph convention divides each voter’s vote equally among closest remaining candidates, and their exclusion-zone definition quantifies over all elimination tie-breaking orders. These match the question’s conventions. [Published paper, Definition 1, graph-voting definition, and Theorem 3](https://ojs.aaai.org/index.php/AAAI/article/download/38775/42737).

The hardness construction also satisfies the graph restrictions here: its set and winning vertices form a clique, and every other vertex has an edge to that clique. Hence it is connected; its edges are simple, undirected, and unweighted. Its designated set contains two vertices, so is nonempty. [Extended paper, Appendix A.2](https://arxiv.org/pdf/2502.16719).

Given an instance \((G,S)\) of \(\mathcal U\), keep \(G\) and \(S\), list every vertex as a distinct location type, and assign each mass \(1/m\). These masses are positive binary rationals and sum to \(1\).

For any nonempty remaining candidate set \(R\), define
\[ \]
the closest-candidate set using inline notation: \(N_R(p)=\{c\in R:d_G(p,c)=\min_{z\in R}d_G(p,z)\}\). The unit-voter score of \(c\in R\) is \(v_R(c)=\sum_{p:\,c\in N_R(p)}1/|N_R(p)|\). Its score in the constructed rational-mass instance is therefore \(\sigma_R(c)=v_R(c)/m\).

Multiplication by the positive constant \(1/m\) preserves every score comparison and equality. Thus every remaining set has exactly the same eligible eliminations in both instances. Induction over the elimination rounds proves that their possible elimination sequences, and hence their possible winners, coincide.

Consequently, \((G,S)\in\mathcal U\) if and only if its constructed instance belongs to \(\mathcal Q\). If the source input length is \(L_0\), the construction takes \(O(L_0+m\log(m+1))\) bit operations and produces length \(O(L_0+m\log(m+1))\), with \(\tau=m\). This proves \(\mathrm{coNP}\)-hardness.

2. A certificate for failure

We next prove membership in \(\mathrm{coNP}\), including exact-arithmetic bounds.

Lemma. The set \(S\) fails to be an exclusion zone if and only if there exist \(u\in S\) and a nonempty set \(X\subseteq P\setminus S\) such that \(\sigma_{\{u\}\cup X}(u)\leq \sigma_{\{u\}\cup X}(x)\) for every \(x\in X\).

Proof. Suppose an election containing a candidate in \(S\) has a possible winner outside \(S\). Fix an elimination sequence producing that winner. Let \(u\) be the last candidate from \(S\) eliminated, and consider the remaining set immediately before its elimination. This set is \(\{u\}\cup X\), where \(X\subseteq P\setminus S\) is nonempty because it contains the eventual winner. Since eliminating \(u\) is legal, its score is minimum.

Conversely, suppose such \(u,X\) exist. Start an election with candidate set \(\{u\}\cup X\). The inequalities permit eliminating \(u\) first, including when its score ties for minimum. All remaining candidates belong to \(P\setminus S\), so every continuation has a winner outside \(S\). This violates the exclusion-zone condition. \(\square\)

A certificate therefore consists of \(u\) and \(X\), requiring \(O(m\log(m+1))\) bits.

3. Exact verification and running time

Write the listed masses as \(a_i/b_i\), with positive integers \(a_i,b_i\), for \(1\leq i\leq\tau\). Define \(D=\prod_{i=1}^{\tau}b_i\), \(H=m!\), and \(Q=DH\).

The bit length of \(Q\) is \(O(L+m\log(m+1))\): the sum of the denominator bit lengths is at most \(L\), and \(m!\leq m^m\).

For each type, precompute the integer \(A_i=a_i(D/b_i)H\). For a tested remaining set \(R\), let \(k_i=|N_R(p_i)|\). Since \(1\leq k_i\leq m\), we have \(k_i\mid H\). Thus \(A_i/k_i\) is an integer, and the exact scaled score is \(Q\sigma_R(c)=\sum_{i:\,c\in N_R(p_i)}A_i/k_i\).

All these scores are nonnegative and at most \(Q\), because the total mass is \(1\). Moreover, \(A_i\leq Q\). Consequently, the arithmetic uses integers with \(O(L+m\log(m+1))\) bits; no numerical approximation is needed.

Let \(B=L+m\lceil\log_2(m+1)\rceil+3\). Breadth-first search from each supported location computes all required distances in \(O(\tau(m+|E|))\) graph operations. Since the graph is simple, \(|E|\leq m(m-1)/2\). Scanning \(R=\{u\}\cup X\) for each supported type determines its nearest candidates, after which integer additions and divisions compute the scores.

Using elementary integer arithmetic, a conservative bound for preprocessing and certificate verification is \(O(L+\tau m^2B^2)\) bit operations. This is polynomial in \(m,\tau,L\). The lemma therefore proves \(\mathcal Q\in\mathrm{coNP}\).

Together with Section 1, this establishes \(\mathrm{coNP}\)-completeness.

4. The requested Turing hardness

Because \(\mathcal U\) is \(\mathrm{coNP}\)-complete, its complement is \(\mathrm{NP}\)-complete. An algorithm with an oracle for \(\mathcal Q\) decides that complement by constructing the uniform-mass instance, making one oracle query, and reversing the answer.

This is a polynomial-time Turing reduction. Composing it with reductions to the \(\mathrm{NP}\)-complete complement proves the requested \(\mathrm{NP}\)-hardness.

⟨structured verdict parsed — rendered above⟩

The argument resolves the assigned problem: it establishes \(\mathrm{coNP}\)-completeness and therefore the requested \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions. I found no substantive mathematical gap. There is one minor formatting defect.

1. The cited hardness result applies

The published paper’s Definition 1 quantifies over every candidate configuration intersecting the proposed exclusion zone and all tie-breaking orders. Its graph-voting convention gives each vertex one voter whose vote is divided equally among the closest candidates. Theorem 3 states that exclusion-zone verification is \(\mathrm{coNP}\)-complete. These are the conventions needed here. [Published paper, Definitions 1 and 3 and Theorem 3](https://ojs.aaai.org/index.php/AAAI/article/download/38775/42737).

The restriction to connected simple undirected unweighted graphs is also justified. In the cited construction, the set and winning vertices form a clique. Every item vertex, set-item vertex, and bonus vertex has an edge to this clique. The specified edges are undirected and require neither loops nor parallel edges, and the designated zone consists of two vertices. Thus the hard family satisfies the target’s graph and nonemptiness restrictions. [Extended paper, Appendix A.2](https://arxiv.org/pdf/2502.16719).

The prover appropriately invokes an established theorem; it does not need to reproduce that theorem’s proof.

2. The uniform-mass reduction is correct

Listing all vertices gives support size \(\tau=m\), which is permitted by the task. Each mass \(1/m\) is a positive rational representable by a binary numerator and denominator, and the masses sum to one.

For every nonempty remaining set \(R\), the closest-candidate sets are unchanged because the graph and candidate locations are unchanged. The displayed score identity
\[ \sigma_R(c)=v_R(c)/m \]
is correct: every individual contribution is multiplied by \(1/m\).

Since this factor is positive, the minimum-score candidates, including all ties, coincide in every remaining set. The induction over rounds therefore preserves every legal elimination sequence and every possible winner. This proves the required equivalence for exclusion-zone membership, including its universal quantification over candidate sets and winners.

The construction writes \(m\) location identifiers and \(m\) copies of a rational with bit length \(O(\log(m+1))\). The stated construction time and output-length bounds are valid for an ordinary explicit graph encoding. Consequently, the transfer establishes \(\mathrm{coNP}\)-hardness under polynomial-time many-one reductions.

3. The failure-certificate lemma is correct

Both directions hold with the stated quantifiers.

• Necessity: In a sequence ending outside \(S\), some candidate from \(S\) must be eliminated. Immediately before the last such elimination, exactly one remaining candidate belongs to \(S\). The remaining outside set is nonempty because it contains the eventual winner. Legal elimination gives precisely the stated minimum-score inequalities.
• Sufficiency: The inequalities authorize eliminating \(u\) first from the proposed candidate set. This includes equality because tied minimum candidates may be chosen. Thereafter all candidates are outside \(S\), and the finite elimination process necessarily ends with an outside winner.

The argument correctly uses recomputed shares: the inequalities concern the actual remaining set, without depending on earlier rounds.

The certificate length \(O(m\log(m+1))\) is sufficient. As usual, the verifier must check that the supplied identifiers describe \(u\in S\) and a nonempty set \(X\subseteq P\setminus S\); these are routine input checks.

The degenerate cases cause no problem. If \(S=P\), no such nonempty \(X\) exists, consistently with automatic exclusion-zone membership. If \(m=1\), the same observation applies.

4. The exact-arithmetic bounds are correct

The product \(D\) is divisible by every \(b_i\), and every possible splitting count \(k_i\) divides \(H=m!\). Thus all scaled contributions \(A_i/k_i\) are integers, and the scaled-score formula is exact.

The bit-length estimate follows from the total encoded denominator length and \(m!\leq m^m\). Positivity and total mass one imply both \(A_i\leq Q\) and \(Q\sigma_R(c)\leq Q\). Partial score sums also obey this bound because all contributions are nonnegative.

The preprocessing and verification bound
\[ O\!\left(L+\tau m^2B^2\right) \]
is conservative but valid. It accommodates distance computation, factorial and denominator-product construction, elementary integer multiplication and division, score accumulation, and comparisons. Connectedness ensures all required distances are finite. Zero-mass vertices remain eligible candidates and are included when scanning \(R\), as required.

Therefore failure has a polynomial-time verifiable certificate, establishing membership in \(\mathrm{coNP}\).

5. The Turing-hardness conclusion is correct

The complement of the cited \(\mathrm{coNP}\)-complete language is \(\mathrm{NP}\)-complete. The uniform-mass transformation followed by one oracle query and reversal of its answer decides that complement. This is a polynomial-time Turing reduction, and composing it with the defining reductions to that \(\mathrm{NP}\)-complete language gives the requested hardness.

The additional assertion that the problem belongs to \(\mathrm{P}\) if and only if \(\mathrm{P}=\mathrm{NP}\) also follows from the established completeness.

6. Minor issue and minimum feedback

Minor — Section 1, introduction of \(N_R(p)\): The text contains an empty display after “define,” followed by the actual definition inline. This is a formatting defect, not an ambiguous mathematical definition.

Minimum repair: Delete the empty display and connect the introductory phrase directly to the existing definition. No additional lemma, hypothesis, or mathematical argument is needed.

⟨structured verdict parsed — rendered above⟩