| paper | d4-conf-aaai-2026-2989 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions; hence \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
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.
Each graph location \(p\in P\) is a voter type with mass \(\mu_p\) and a graph-distance preference order over candidate locations. Candidate sites remain indivisible; IRV tallies the mass assigned to each remaining site's nearest-candidate region, splitting mass equally on distance ties. The decision asks whether the set \(S\) contains every possible winner whenever a candidate from \(S\) runs.
The mirror covers the exact graph exclusion and minimal-zone problems in Theorems 3 and 4. It leaves the geometric results and the graph approximation, parameterized, and graph-family results unaddressed.
The strongest mirror is the paper’s graph-voting problem. Its facility-closure interpretation makes a high-multiplicity population natural: take a graph \(G=(P,E)\) of neighborhoods or possible facility sites, with many customers at each location. Customers at \(p\) share the same complete weak preference order over sites, ordered by graph distance. Represent them by rational masses \(\mu_p\ge 0\), where \(\sum_{p\in P}\mu_p=1\). The support size \(\tau\) is the number of occupied location types; the customer population can be much larger. A candidate configuration remains a subset \(C\subseteq P\), with at most one candidate at each site. At every IRV round, each type’s mass goes equally to its nearest remaining candidates, and any candidate tied for the fewest votes may be eliminated. This preserves the paper’s elimination process and its split treatment of distance ties, while making the population a mass distribution.
My lead is Mass-IRV-Exclusion. An instance is \((G,\mu,S)\), with \(S\subseteq P\). Decide whether, for every candidate set \(C\subseteq P\) with \(C\cap S\ne\varnothing\), every winner obtainable under any permitted tie-breaking sequence lies in \(S\). A no-instance has a concrete witness: a candidate set intersecting \(S\) and an elimination tie-break sequence ending outside \(S\).
The anchor is Theorem 3, proved in this paper: IRV-Exclusion on an unweighted graph, with one uniform voter at each node, is co-NP-complete. The authors prove this by reducing from restricted exact cover by 3-sets; the constructed two-node set is an exclusion zone exactly when the instance has no exact cover. The mass version should also be co-NP-complete. Setting \(\mu_p=1/|P|\) recovers the paper’s model: normalization scales every vote share equally, so it preserves all eliminations and ties. For membership in co-NP, a counterexample candidate set and tie-break sequence can be checked in polynomial time using graph distances and rational vote arithmetic. This is a Class B mirror: the hard combinatorics lie in the candidate positions and their possible configurations, so population masses do not remove them.
A second, distinct anchor is Theorem 4, also proved here: computing a graph’s minimal IRV exclusion zone is NP-hard. Its proof uses the construction from Theorem 3 to recover the exact-cover answer from the minimal zone. The mass analogue, Mass-Min-IRV-Exclusion, takes \((G,\mu)\) and outputs the unique inclusion-minimal set \(S^*\) such that every candidate configuration meeting \(S^*\) has all possible IRV winners in \(S^*\). The paper’s Proposition 2 ensures this set is well-defined. The mass problem remains NP-hard by the same uniform-mass restriction, and I expect it to be Class B as well. This anchor matters on its own because it asks for the whole favored region, rather than checking a proposed region.
The setting is one the authors could plausibly recognize: their graph section explicitly describes facilities closing one by one as customers move to their nearest remaining facility. Replacing unit counts by customer masses at graph locations leaves that process intact. Clearing the denominators of \(\mu\) recovers a finite population of repeated customers, so this is a high-multiplicity formulation rather than a fractional-candidate or fractional-outcome variant. It covers the exact graph exclusion and minimal-zone problems of Theorems 3–4. It does not claim to mirror the geometric results in Theorems 1–2, which already study continuous voter distributions but make structural claims rather than complexity claims; nor does it establish weighted versions of the approximation and parameterized results in Theorems 5–6.
The strongest follow-up questions are whether the paper’s parameterization by the number of positions outside \(S\) still gives fixed-parameter tractability with rational masses, and whether a small number \(\tau\) of occupied types yields a useful algorithm. Weighted versions of the paper’s randomized approximation guarantee are also natural to investigate.
The weak point is that this mirror is more convincing as a hardness-boundary result than as a tractability story: the uniform instances already remain hard, and the mass formulation may offer no computational advantage. Also, the paper’s school-network example has one named student per node; the large-cohort story is more persuasive for customers aggregated at neighborhood sites than for those individual friendships. That limits the scenario’s breadth, but it does not make the graph-mass question artificial—or weaken the case that the paper’s exact computational problem has a sensible continuous-population form.
The strongest case against this mirror is about its reach, not its coherence. The paper’s school-network story has one student at each node, and collapsing students into location masses would discard their individual positions in the friendship network. That story does not support high multiplicity unless the network itself has large cohorts of indistinguishable students at each location.
But the paper supplies a better story: facility closure, where customers choose the nearest remaining facility. A graph can represent neighborhoods or service locations, with many customers at each location. Those customers share the same complete preferences, determined by graph distance. Their mass affects vote shares, and the exclusion-zone question still asks which locations can win against which candidate configurations. The population is the continuous object; the graph and candidate sites remain discrete, as the programme allows. This is a credible high-multiplicity regime.
That leaves no solid way to defeat Theorem 3. With equal rational mass at every node, the weighted model reproduces its elections exactly, including possible tie-breaking outcomes. A counterexample to exclusion can still be checked in polynomial time, and the paper’s reduction supplies the hardness. The mirror asks a well-posed question even if the uniform instances already establish that the general problem is hard.
Theorem 4 survives for the same reason: on uniform masses, the minimal exclusion zone is exactly the paper’s minimal zone, so its NP-hardness carries over. This is not an independent reason that the mirror is especially valuable—the two anchors concern closely related tasks—but the programme explicitly treats transferred hardness as a meaningful boundary result.
So the honest negative case is weak. The mirror may not open an obvious continuous-optimization route, and the customer-cohort scenario is narrower than the paper’s broader friendship-network framing. Those points limit its reach; they do not show that no worthwhile scenario exists. None of the available decisive objections applies: the paper has named computational results, the facility-location interpretation supports multiplicity, the objective does not track customer identities, and no continuous computational treatment of these graph problems is given here. I cannot honestly argue the universal claim that there is no worthwhile continuous mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.