d4-conf-ijcai-2020-0257

The strongest honest case is that this paper has a natural high-multiplicity mirror for its connected-committee problems, even though the hardness results suggest that continuity may not make them easier.

Consider a large professional association selecting \(k\) candidates for a committee whose members need communication links between them. Association members rank the candidates; edges in the candidate graph represent those links. With \(100{,}000\) or more members but, say, dozens or hundreds of recurring complete rankings, a voter type is a ranking \(t\), and its mass \(\mu_t\) is the fraction of members holding it. This gives many agents but relatively small support \(\tau\), while preserving the paper’s committee, preference, and candidate-network questions. It is a more convincing population regime than the paper’s example where “voters” are a finite set of required skills.

My lead anchor is Theorem 3. “CONN-k-BORDA is NP-complete.” This is the paper’s own theorem, rather than a result attributed to another source; its proof is not included in the supplied text. It says that deciding whether there is a size-\(k\), connected committee with Borda score at least the given threshold is NP-complete.

The continuous problem I would hand to a prover is \(\mathrm{CONN}\text{-}k\text{-Borda}_{\infty}\). An instance gives candidates \(C\), an undirected candidate graph \(H\), a committee size \(k\), a rational threshold \(q\), and a finite-support distribution \(\mu\) over complete rankings of \(C\), with binary-rational masses summing to \(1\). For ranking \(t\), let \(\operatorname{pos}_t(c)\) be the position of candidate \(c\), and set
\[ \mathrm{sc}_{\mu}(c)=\sum_t \mu_t\bigl(m-\operatorname{pos}_t(c)\bigr). \]
The question is whether there is a set \(S\subseteq C\), with \(|S|=k\), such that \(H[S]\) is connected and
\[ \sum_{c\in S}\mathrm{sc}_{\mu}(c)\ge q. \]
A solution is such a committee \(S\); the optimization version maximizes the left-hand side over connected size-\(k\) committees.

Theorem 3’s hardness transfers directly. Given a discrete election with \(n\) voters, set \(\mu_t\) to the fraction of voters with ranking \(t\), and set \(q=s/n\) for the original score threshold \(s\). Every committee has continuous score exactly its discrete score divided by \(n\), and connectedness is unchanged. This is a polynomial-size transformation with \(\tau\le n\). The continuous decision problem is also in NP: a proposed committee can be checked for size, connectivity, and threshold in polynomial time using the rational input. So the expected outcome is Class B: NP-completeness survives through the discrete embedding, not continuum-specific hardness. The paper’s Theorem 4 also gives a natural follow-up: determine which of its parameterized algorithms carry over with dependence on \(k\), \(\tau\), and the mass bit length.

A second, genuinely useful anchor is Theorem 2. “CONN-CC is NP-complete for SP profiles.” This is also the paper’s own result, not a cited theorem; the supplied text gives the statement but not its proof. It establishes NP-completeness even when the rankings are single-peaked.

Its mirror, \(\mathrm{CONN}\text{-CC}_{\infty}^{\mathrm{SP}}\), has the same \(C,H,k\) setup, plus a witnessed common axis \(\pi\), a distribution \(\mu\) supported only on rankings single-peaked with respect to \(\pi\), and a rational threshold \(q\). Define
\[ \mathrm{CC}_{\mu}(S) =\sum_t\mu_t\max_{c\in S}\bigl(m-\operatorname{pos}_t(c)\bigr). \]
The question is whether some connected size-\(k\) set \(S\) has \(\mathrm{CC}_{\mu}(S)\ge q\); the solution is the committee \(S\). For a discrete single-peaked profile, its empirical distribution and the threshold \(q=s/n\) preserve every yes/no answer, so NP-hardness transfers; the committee remains a polynomial-size certificate. The expected classification is again Class B. This anchor makes the case sturdier by showing the population mirror can retain a meaningful preference restriction rather than requiring arbitrary rankings.

The soft spot is that a continuous population is a good description only in the large-electorate regime. The paper also emphasizes settings with few voters, and its skill-based story need not describe a population of people at all. In the association scenario, though, voters really are numerous, and the committee and graph constraints remain exactly the paper’s. These mirrors therefore seem like questions the authors could recognize as their problems. Their main value is a precise high-multiplicity complexity question; the cited hardness results suggest that, for these anchors, continuization preserves the challenge rather than dissolving it.