| paper | d4-conf-aaai-2015-0704 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: For every fixed \(p\ge3\), the problem is \(\mathrm{NP}\)-complete and \(\mathrm{W[1]}\)-hard parameterized by \(K\); it is not \(\mathrm{FPT}\) unless \(\mathrm{FPT}=\mathrm{W[1]}\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 1, part (1)
statement extracted from the paper’s text layer
For fixed \(p\ge 3\), an instance gives a candidate set \(C\), a committee bound \(K\), a finite support \(\mathcal A\) of approval types \(A\subseteq C\) with \(|A|\le p\), binary-rational masses \(\mu_A>0\) summing to \(1\), and a rational threshold \(q\). Is there a committee \(W\subseteq C\), \(|W|\le K\), such that \(\sum_{A:A\cap W\ne\varnothing}\mu_A\ge q\)?
Represent the electorate by supported approval types \(A\) with rational masses \(\mu_A\). Choose binary committee variables \(y_c\) with \(\sum_{c\in C}y_c\le K\), and maximize \(\sum_{A\in\mathcal A}\mu_A z_A\), where \(z_A=1\) exactly when some approved candidate is selected. Impose the paper's upper-frequency condition as \(|A|\le p\) for each supported type.
The opponent notes that weighted maximum coverage is established prior art, which may limit novelty; under the programme's criteria, that can inform the prover's target but does not undermine the population mirror.
fatal: False
The mirror covers Theorem 1, part (1), through exact bounded-frequency weighted coverage, and raises the rational-mass analogue of Theorem 3. It leaves the lower-frequency results, uncovered-element parameterizations, and unrestricted-case approximation scheme outside its stated scope.
The strongest mirror keeps the committee indivisible and changes only how the electorate is represented. Imagine a large association choosing \(K\) people for a committee from a fixed candidate slate. Each voter approves at most \(p\) candidates, and many voters use the same approval ballot. A type is one complete approval set \(A\subseteq C\); its mass \(\mu_A\) is the fraction of the electorate with that ballot. The instance lists only the \(\tau\) supported ballot types and their binary rational masses, with \(\sum_A\mu_A=1\).
This is the paper’s Chamberlin–Courant question in population form: choose candidates that represent as much of the electorate as possible. For a committee \(W\subseteq C\), \(|W|\le K\), the represented mass is
\[
F_\mu(W)=\sum_{A:A\cap W\ne\varnothing}\mu_A.
\]
Each voter still gets utility \(1\) if some selected candidate is approved and \(0\) otherwise. Only the objective is expressed as a population fraction rather than a headcount.
My lead is Exact Type-Continuous Approval CC. Its instance consists of \(C\), \(K\), a supported collection of approval types \(\mathcal A\) with rational masses \(\mu_A\), and a rational threshold \(q\). For fixed \(p\ge3\), require \(|A|\le p\) for every supported type. The question is whether there is a committee \(W\) of at most \(K\) candidates with \(F_\mu(W)\ge q\); a solution is such a committee. Equivalently, its optimization version returns a committee maximizing \(F_\mu\).
The anchor is Theorem 1, part (1): for every constant \(p>2\), MaxCover with element frequencies at most \(p\) is W[1]-complete when parameterized by the number \(K\) of sets selected. This is the paper’s classification result; its hardness uses the cited W[1]-hardness of MaxVertexCover from Guo et al. (2007). The mirror preserves that combinatorics. Given a discrete instance with elements \(e\) and sets corresponding to candidates, make \(e\)’s approval type \(A_e\) the candidates whose sets contain \(e\), and assign each resulting type mass \(\mu_A=|\{e:A_e=A\}|/|N|\). Every committee’s represented mass is exactly its original coverage divided by \(|N|\); threshold \(T\) maps to \(q=T/|N|\). Thus the continuous decision problem is W[1]-hard in \(K\) for fixed \(p\ge3\). I expect Class B for exact winner determination: the source hardness survives in the population formulation.
The regime is plausible for recurring approval ballots: for example, a large membership election where voters approve a small number of candidates and substantial constituencies share approval patterns. The population can be much larger than the support: replicating voters leaves \(\mu\) and the optimization unchanged while making \(N/\tau\) arbitrarily large. The model uses complete types for everything the rule considers—here, the approval ballot—so aggregation does not discard distinctions relevant to representation.
A second, useful anchor is Theorem 3. It states that when every element appears in at most \(p\) sets, Algorithm 1 returns a \(\beta\)-approximate MaxCover solution in time
\[
\operatorname{poly}(n,m)\binom{\left\lceil 2pK/(1-\beta)+K\right\rceil}{K}.
\]
The paper proves this for unweighted elements. Its continuous counterpart is the \(\beta\)-Approximate Type-Continuous Approval CC problem: on the same type-mass input, return a committee \(W\), \(|W|\le K\), satisfying \(F_\mu(W)\ge\beta\max_{|W'|\le K}F_\mu(W')\). I expect Class A for fixed \(p\) and \(\beta\): the theorem’s exchange argument appears to extend by replacing element counts with rational mass. Rank candidates by their total approved mass, and the frequency bound still controls weighted incidence, since each unit of type mass appears in at most \(p\) candidate sets. That would give running time \(\operatorname{poly}(m,\tau,L)\binom{\left\lceil 2pK/(1-\beta)+K\right\rceil}{K}\), where \(L\) is the mass encoding length. This weighted guarantee is a result to establish for the mirror; it is not what Theorem 3 already states.
The lead is Theorem 1’s exact hardness result. Theorem 3 gives a worthwhile second question because it tests whether the paper’s approximation algorithm survives the move from equal voter weights to type masses. Together they cover the bounded-approval, upper-frequency MaxCover setting. They do not claim a mirror for the paper’s lower-bounded-frequency results, its uncovered-element parameterizations, or its unrestricted-case approximation scheme.
The weakest point is that the hardness reduction need not use a small support: it establishes hardness for the weighted population problem, but does not show that a particularly small \(\tau\) is difficult. The mirror therefore says that exact computation remains hard in \(K\), not that population aggregation itself creates hardness. A natural next question is how complexity changes with \(\tau\); an exact dynamic program over the \(2^\tau\) sets of covered types already gives an FPT algorithm in \(\tau\). That limitation does not undo the mirror: it identifies which parameter the paper’s hardness survives and which population-size dependence the continuous representation removes.
The strongest skeptical case is that the proposed mirror changes the objective’s units, not its combinatorial structure. For a finite support of approval types, \(F_\mu(W)\) is weighted MaxCover: each type is an element with rational weight, and each candidate covers the types that approve it. Weighted coverage is already a standard optimization model; for example, Khuller, Moss, and Naor study maximum coverage over weighted elements ([paper](https://www.sciencedirect.com/science/article/pii/S0020-0190(99)00031-9)). So this mirror brings no obvious new continuous machinery to the problem.
That objection does not defeat Theorem 1. Its hardness reduction works directly: give each original element mass \(1/n\), and set \(q=T/n\). Merging elements with identical approval ballots preserves every committee’s coverage value. The result is still W[1]-hard in \(K\), even though its instances may have large populations relative to their support. Restricting to small \(\tau\) would yield a useful separate regime—indeed, a dynamic program over the \(2^\tau\) possible unions of covered types runs in \(O(mK2^\tau)\)—but that does not remove the broader mirror.
Nor does Theorem 3 fall to a sound objection. Its exchange argument appears to extend to rational type masses: replace cardinalities by total mass, and use the frequency bound to control weighted incidence. The resulting algorithm may be a routine weighted generalization rather than a new continuous-optimization technique, but that is a criticism of novelty, not of whether the mirror is a well-posed computational question.
The honest negative case is therefore weak under ChoCo’s criteria. The model has a natural high-multiplicity scenario, the approval ballot is a complete type for this rule, and the represented fraction remains meaningful in the limit. Weighted-coverage prior art is a neighboring formulation, not evidence that this paper already studied a continuous population. I cannot honestly defeat either anchor: the proposed mirror looks worthwhile, though its main contribution may be to establish how the paper’s results behave under rational population masses rather than to unlock a new algorithmic toolbox.
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.