d4-conf-aaai-2026-2001 (d4-conf-aaai-2026-2001)

Given candidates \(C\), a finite support \(T\) of strict rankings with positive binary-rational masses \(\mu_t\) summing to \(1\), and bounds \(b\), \(k\), and rational threshold \(\alpha\), is there a partition of \(C\) into at most \(k\) nonempty parts \(X_i\), each of size at most \(b\), such that for every part, \(\sum_{t\in T:\,t\text{ ranks }X_i\text{ consecutively}}\mu_t\ge\alpha\)?

Given a nonempty candidate set \(C\) with \(m=|C|\), a society is given by its support: a list \(T\) of \(\tau\) distinct strict rankings of all candidates, each with positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings.
The remaining inputs are positive binary-encoded integers \(b,k\) and a binary-rational threshold \(0<\alpha\leq1\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L,b,k\).
A ranking recognizes a nonempty set \(X\subseteq C\) when its members occupy consecutive positions, in any internal order. Define \(r(X)=\sum_{t\in T:\,t\text{ recognizes }X}\mu_t\).
The decision problem asks whether \(C\) has a partition into \(s\leq k\) nonempty parts \(X_1,\ldots,X_s\), each satisfying \(|X_i|\leq b\) and \(r(X_i)\geq\alpha\). The recognizing types may differ between parts.

Is this rational-mass independent-clone partition problem solvable in polynomial time, or is it \(\mathsf{NP}\)-hard?

For explicitly listed voters, Independent-Clone Partition is \(\mathsf{NP}\)-complete even with \(b=3\), recognition required from at least \(w=2\) voters, and exactly \(n=14\) voters; it admits an \(\mathsf{XP}\) algorithm parameterized by the number of parts. [Source](https://arxiv.org/html/2509.11261v1)
No separate complexity classification for the stated rational-mass formulation was located.

Result. The problem is \(\mathsf{NP}\)-complete, even when \(b=3\), \(\tau\leq14\), and \(\alpha=1/8\). Hardness holds with dyadic masses whose denominators are all \(128\), so it does not depend on allowing arbitrary rational denominators.

Membership in \(\mathsf{NP}\). A certificate assigns each candidate a part label from \(\{1,\ldots,m\}\). Its length is \(O(m\log(m+1))\). We check that the resulting nonempty parts \(X_1,\ldots,X_s\) satisfy \(s\leq k\) and \(|X_i|\leq b\).

For each ranking \(t\), let \(p_t(c)\) denote the position of candidate \(c\). Because all positions are distinct, \(t\) recognizes a nonempty set \(X\) exactly when
\(\max_{c\in X}p_t(c)-\min_{c\in X}p_t(c)+1=|X|\).
Indeed, the interval between the two extreme positions contains exactly that many positions; equality means that every position in it belongs to \(X\).

Precompute the position tables. Scanning all candidates once per ranking computes the minimum and maximum positions for every part, using \(O(\tau m\log(m+1))\) bit operations.

Recognition masses can be compared exactly in polynomial time. Write \(\mu_t=a_t/q_t\) and \(\alpha=u/v\), with binary-encoded positive integer numerators and denominators. Set
\(D=v\prod_{t\in T}q_t\),
\(W_t=a_t(D/q_t)\), and \(A=u(D/v)\).
The integer \(D\) has \(O(L)\) bits. Since each mass and the threshold are at most one, \(W_t\) and \(A\) also have \(O(L)\) bits. For every part \(X_i\), the threshold condition is precisely
\(\sum_{t:\,t\text{ recognizes }X_i}W_t\geq A\).

Using schoolbook integer arithmetic, preprocessing takes \(O(L^3)\) bit operations, and verification thereafter takes \(O(\tau mL)\). Thus a conservative verification bound is \(O(L^3+\tau mL)\). The binary encodings of \(b\) and \(k\) require only comparisons; no iteration up to their numerical values is needed. This proves membership in \(\mathsf{NP}\).

Hardness reduction. We use the following established theorem: explicitly listed Independent-Clone Partition is \(\mathsf{NP}\)-complete with fourteen voters, maximum part size three, and recognition required from at least two voters. Its partition bound is “at most,” exactly as in the present task. See [Theorem 4.6 and the problem definition in Section 2](https://arxiv.org/html/2509.11261v1).

Take such a source instance with rankings \(v_1,\ldots,v_{14}\), candidate set \(C\), and part bound \(k\). Keep \(C\), \(b=3\), and \(k\). Assign auxiliary weights
\(\lambda_1=\lambda_2=10/128\) and
\(\lambda_j=9/128\) for \(3\leq j\leq14\).
These weights are positive and sum to one, since
\(2\cdot10+12\cdot9=128\).

Now merge voters with identical rankings. Let \(T\) contain precisely the distinct rankings, and give each ranking \(t\) mass
\(\mu_t=\sum_{j:\,v_j=t}\lambda_j\).
Finally, set \(\alpha=1/8=16/128\).

This produces a valid support representation: rankings are distinct, masses are positive, their sum is one, and \(\tau\leq14\). Every mass has a constant-length dyadic representation.

For any nonempty \(X\subseteq C\), merging preserves its total recognition weight:
\(r(X)=\sum_{j:\,v_j\text{ recognizes }X}\lambda_j\).
If at most one source voter recognizes \(X\), then
\(r(X)\leq10/128<16/128=\alpha\).
If at least two source voters recognize \(X\), then
\(r(X)\geq18/128>16/128=\alpha\).
Consequently,
\(r(X)\geq\alpha\)
holds if and only if at least two source voters recognize \(X\).

Thus every part is admissible in the constructed instance exactly when it is admissible in the source instance. Candidate sets, size bounds, and part bounds agree, so the two instances have identical feasible partitions. In particular, recognizing voters may differ between parts in both formulations.

There are only fourteen rankings to compare and merge. The transformation takes \(O(L_{\mathrm{src}})\) time and produces \(O(L_{\mathrm{src}})\) output bits, where \(L_{\mathrm{src}}\) is the source input length. Empty source candidate sets, if allowed, are trivially feasible and can be mapped separately to a fixed singleton yes-instance. Therefore the nonempty-candidate requirement causes no difficulty.

This is a polynomial many-one reduction, proving \(\mathsf{NP}\)-hardness. Together with membership, it establishes \(\mathsf{NP}\)-completeness.

An explicit support-based \(\mathsf{XP}\) bound. The rational representation also permits an algorithm parameterized by \(k\), without expanding masses into voters.

Put \(B=\min\{b,m\}\) and \(K=\min\{k,m\}\). Every admissible part has positive recognition mass, because \(\alpha>0\), and therefore occurs as an interval in some listed ranking. Enumerate all intervals of lengths at most \(B\) in every ranking. Their number, counting duplicates, is
\(N=\tau\sum_{\ell=1}^{B}(m-\ell+1)\leq\tau mB\).

Enumerate ordered \(K\)-tuples of these interval occurrences together with an empty padding option. For each tuple, first check that its nonempty entries have total size \(m\); then check disjointness and the recognition thresholds. Every feasible partition appears in this enumeration: choose one recognizing ranking for each part and pad the remaining entries.

Precomputing the integer weights above once gives the conservative running-time bound
\(O\!\left(L^3+(\tau m\min\{b,m\}+1)^{\min\{k,m\}}\tau mL\right)\).
This is polynomial for every fixed \(k\), establishing \(\mathsf{XP}\) membership parameterized by the number of allowed parts.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves the task. The cited hardness theorem matches the source problem, the reduction preserves feasible partitions, and both stated algorithmic bounds are justified. No major or minor mathematical issues were found.

1. Verification of the cited theorem

The prover states precisely the external result it uses: Independent-Clone Partition is \(\mathsf{NP}\)-complete with exactly fourteen voters, maximum part size three, and recognition by at least two voters.

This matches Theorem 4.6 of the cited paper. Section 2 defines the partition bound as “at most” the given number of parts, and permits different recognizing groups for different parts. Thus the theorem applies to the source formulation used in the reduction. [Source: Section 2 and Theorem 4.6](https://arxiv.org/html/2509.11261v1)

The distinction between fourteen voters and fourteen distinct rankings is handled explicitly by the subsequent merging step.

2. Membership in \(\mathsf{NP}\)

Certificate. Assigning each candidate a label from \(\{1,\ldots,m\}\) specifies a partition through the nonempty label classes. The claimed certificate length, \(O(m\log(m+1))\), is polynomial. Unused labels cause no problem: the verifier counts only nonempty parts.

The checks \(s\leq k\) and \(|X_i|\leq b\) enforce the required partition restrictions. They require comparisons with the binary inputs, without iterating up to their numerical values.

Recognition test. For a nonempty set \(X\), the condition
\[ \max_{c\in X}p_t(c)-\min_{c\in X}p_t(c)+1=|X| \]
is exactly the condition that its members occupy consecutive positions. Distinctness of positions ensures that the interval between the extreme positions contains no outside candidate when equality holds. This also correctly handles singleton parts.

Exact rational arithmetic. The definitions
\[ D=v\prod_{t\in T}q_t,\qquad W_t=a_t(D/q_t),\qquad A=u(D/v) \]
use integer divisions because each divisor divides \(D\). Multiplication of the recognition inequality by the positive integer \(D\) preserves its direction.

The bit length of \(D\) is bounded by the sum of the denominator bit lengths, hence is \(O(L)\). Since \(0<\mu_t\leq1\) and \(0<\alpha\leq1\), each \(W_t\) and \(A\) is at most \(D\). Recognition sums are also at most \(D\), because the masses sum to one. Thus all critical arithmetic has polynomial bit length.

Running time. Schoolbook arithmetic supports the conservative \(O(L^3)\) preprocessing bound. Recognition checks and integer accumulation fit within \(O(\tau mL)\), including the stated position-scanning cost. Therefore
\[ O(L^3+\tau mL) \]
is a justified verification bound, establishing membership in \(\mathsf{NP}\).

3. Hardness reduction

Normalization and positivity. The auxiliary weights satisfy
\[ 2\cdot10+12\cdot9=128. \]
They are positive and sum to one.

Support representation. Merging identical rankings produces distinct support entries with positive masses summing to one. There are at most fourteen entries. Each mass can be represented with denominator \(128\); reducing fractions is unnecessary for the claimed representation.

Preservation of recognition weight. Voters with identical rankings recognize exactly the same sets. Consequently, replacing them by one support entry whose mass is their combined weight preserves every set’s recognition weight.

Threshold equivalence. The critical inequalities are correct:
\[ \frac{10}{128}<\frac{16}{128}=\frac18 \quad\text{and}\quad \frac{18}{128}>\frac{16}{128}. \]
A set recognized by at most one source voter has weight at most \(10/128\). A set recognized by at least two source voters has weight at least \(18/128\), since every voter’s weight is at least \(9/128\).

Therefore, for every nonempty candidate set, recognition mass at least \(1/8\) is equivalent to recognition by at least two source voters. The equivalence remains valid when recognizing voters have identical rankings.

Partition equivalence. Candidate sets, size bounds, and part bounds are preserved. The threshold equivalence applies separately to every part, so the two instances have exactly the same feasible partitions. No common recognizing group is introduced.

Reduction size and time. Comparing and merging a fixed number of fourteen explicit rankings requires only a constant number of linear scans. The weights have constant-size encodings. Thus the claimed \(O(L_{\mathrm{src}})\) transformation time and output size are justified.

The stated treatment of empty source candidate sets also preserves their answer, should such instances be allowed. The target’s nonempty-candidate requirement is respected.

The reduction therefore establishes \(\mathsf{NP}\)-hardness under all the claimed restrictions. Together with membership, it proves \(\mathsf{NP}\)-completeness.

4. The additional \(\mathsf{XP}\) claim

Enumeration coverage. Since \(\alpha>0\), every admissible part must be recognized by at least one listed ranking. It therefore appears among that ranking’s enumerated intervals.

With \(B=\min\{b,m\}\), the interval count
\[ N=\tau\sum_{\ell=1}^{B}(m-\ell+1)\leq\tau mB \]
is correct, including duplicate occurrences.

Padding and completeness. Any partition of a nonempty \(m\)-candidate set has at most \(m\) parts. Hence \(K=\min\{k,m\}\) provides enough tuple entries for every permitted partition. Empty padding represents unused entries and does not become a partition part.

Acceptance conditions. Enumerated nonempty entries already satisfy the size bound. Pairwise disjointness together with total size \(m\) ensures that they cover \(C\). Checking their recognition thresholds then verifies precisely the required conditions.

Running time. There are \((N+1)^K\) tuples. The preliminary size check is inexpensive; after it passes, only \(m\) candidate occurrences need examination. The per-tuple work fits within \(O(\tau mL)\). Thus the displayed bound
\[ O\!\left(L^3+(\tau m\min\{b,m\}+1)^{\min\{k,m\}}\tau mL\right) \]
is justified and is polynomial for every fixed \(k\).

5. Repair feedback

No repair or additional clarification is needed. The proof establishes the requested complexity classification and its additional support-based \(\mathsf{XP}\) bound.

⟨structured verdict parsed — rendered above⟩