| paper | d4-conf-aaai-2016-0271 |
| 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{NP}\text{-complete}\), even for input trees of diameter at most four or maximum degree at most three. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a candidate set \(C\), an unlabelled tree \(T\) on \(|C|\) vertices, and a finite-support distribution \(\mu\) over strict rankings of \(C\) with positive binary-rational masses, decide whether there is a bijection \(\ell:V(T)\to C\) such that for every \(t\in\operatorname{supp}(\mu)\) and every \(j\in\{1,\ldots,|C|\}\), the vertices labelled by the top \(j\) candidates in \(t\) induce a subtree of \(T\).
The society is a distribution \(\mu\) over complete ranking types; the decision variable is a bijection \(\ell\) from the vertices of the input tree to candidates. The condition is that every top-ranked prefix of every positive-mass type induces a subtree. Mass values identify the positive support but do not otherwise affect this universal condition.
The mirror covers the tree-labelling hardness of Theorem 8; Theorem 9 gives a related regular-tree recognition question, and Theorem 10 has a weighted committee-selection analogue. It leaves the attachment-digraph algorithms and the other recognition results uncontinuized.
The most credible regime is a very large electorate voting over the same finite slate of \(m\) alternatives, where ballots come from a moderate repertoire of complete rankings. There may be \(N\) voters and only \(\tau\) distinct ranking types, with \(N \gg \tau\); type \(t\) has mass \(\mu_t=n_t/N\). This is plausible for large consultations or platform votes shaped by recurring preference patterns, though not for settings where nearly every voter has a unique ranking. The paper’s single-peakedness condition applies to every voter, so the natural continuous version requires every positive-mass type to satisfy it. A rare type can still rule out a shared tree, just as one voter can in the paper’s model.
My lead is the paper’s Theorem 8, proved there: SINGLE-PEAKED TREE LABELLING is NP-complete, even when the input tree has diameter at most four or maximum degree at most three. Its instance is a profile over candidates and an unlabelled tree with the same number of vertices; it asks whether the tree’s vertices can be labelled with candidates so that the profile is single-peaked on that labelled tree.
The continuous problem is Continuous-Support Tree Labelling. Its instance is a candidate set \(C\), a distribution \(\mu\) with finite support of \(\tau\) strict rankings and positive binary-rational masses summing to one, and an unlabelled tree \(T\) on \(|C|\) vertices. It asks for a bijection \(\ell:V(T)\to C\) such that, for every \(t\) with \(\mu_t>0\) and every \(j\), the vertices labelled by the top \(j\) candidates in \(t\) induce a subtree of \(T\). A successful labelling is the solution. This is the paper’s own question about whether a proposed tree topology can host a common single-peaked domain; the population distribution supplies its ranking types and their proportions.
Theorem 8’s hardness carries over directly: replace each input profile \(V\) by \(\mu_t=|\{v\in V:v=t\}|/|V|\). This takes polynomial input size, preserves exactly which types must satisfy the condition, and preserves the restricted tree. Verification of a labelling is polynomial in \(m,\tau\), and the mass bit length \(L\). I therefore expect this mirror to be NP-complete as well: Class B, since the hard combinatorics concern labelling alternatives on a tree, not the number of voters. It also raises natural parameterized questions, such as whether restrictions on \(m\), \(\tau\), or the tree topology yield useful algorithms.
A distinct hardness question comes from Theorem 9, also stated as a result of this paper: deciding whether there exists a positive integer \(k\) such that a profile is single-peaked on some \(k\)-regular tree is NP-complete; the problem is also hard for each fixed \(k\ge4\). Here Continuous Regular-Tree Recognition takes \(C\) and a finite-support distribution \(\mu\), and asks for a positive integer \(k\), a \(k\)-regular tree on \(m\) vertices, and a labelling of that tree by \(C\) that makes every positive-mass type single-peaked. The fixed-\(k\) version fixes \(k\) in advance and asks for such a tree and labelling. The same profile-to-distribution reduction transfers the paper’s hardness, including the fixed-\(k\) cases. This is a separate mirror from Theorem 8: here the tree topology is part of the search, constrained to be regular. I expect hardness to transfer, again because the reduction’s combinatorics live in the alternatives and tree structure. Further questions include which fixed values of \(k\) become tractable and how the answer depends on the number of supported types.
The paper’s Theorem 10, proved there, offers a different kind of mirror. It says that given a profile \(V\), a tree \(T\) on which it is single-peaked with \(\eta\) internal vertices, and a target committee size \(k\), a Borda Chamberlin–Courant winning committee can be found in time \(\operatorname{poly}(n,m,(k+1)^\eta)\); the paper also identifies the algorithm as FPT in \((k,\eta)\). The corresponding continuous problem, Distributional Borda Chamberlin–Courant, takes \(C\), \(\mu\), a compatible candidate-labelled tree \(T\) with \(\eta\) internal vertices, and \(1\le k\le m\). It asks for a size-\(k\) committee \(S\subseteq C\) minimizing
\[
\sum_{t\in\operatorname{supp}(\mu)}
\mu_t\bigl(\operatorname{pos}_t(S)-1\bigr),
\]
where \(\operatorname{pos}_t(S)\) is the position of \(t\)’s highest-ranked committee member. The committee remains a discrete choice; the population objective is its average Borda misrepresentation.
I expect this weighted problem to be tractable, with an FPT algorithm in \((k,\eta)\) and polynomial dependence on \(m,\tau,L\). In the paper’s proof, the relevant counts of voters with each top candidate become their masses under \(\mu\), and the score comparisons become exact rational comparisons. This is a natural mirror for a large electorate selecting a small representative committee, with a known low-branching policy tree. It generates questions about other misrepresentation functions and whether one can combine committee selection with finding a suitable low-\(\eta\) tree.
The weakest point is that the Theorem 8 and 9 mirrors are continuous mainly in representation: their yes/no conditions depend on support, not on the values of the masses. That is still faithful to the paper’s universal condition over voters, and the high-multiplicity regime is sensible for repeated complete ballots. Theorem 10 is the stronger demonstration that the distribution can matter computationally: there, masses directly determine the welfare objective. This case covers Theorems 8, 9, and 10; it does not claim to continuize the paper’s whole framework or every result about attachment digraphs.
The strongest case against is that Theorems 8 and 9 concern which ranking types are present, not how much of the population has each type. In the proposed mirrors, replacing a positive mass by a much larger or smaller positive mass cannot change the answer. Collapsing repeated ballots to their distinct rankings already gives the same yes/no question. A population-sensitive variant—say, finding a labelled tree that makes at least \(1-\varepsilon\) of the mass single-peaked—would use the masses, but it changes the paper’s exact common-domain question into a weighted approximation problem. The paper’s hardness results do not establish that this new objective is worth pursuing.
The same objection applies to Theorem 9: masses do not affect whether the supported types admit a \(k\)-regular tree and a suitable labelling. A version that maximizes the compatible mass could be more faithful to a heterogeneous society, but it is a new optimization problem, not a continuization of the result as stated. These two anchors therefore offer little evidence that continuization changes the computational object.
Theorem 10 is much harder to dismiss. Its distributional Chamberlin–Courant version is natural: committee quality is the expected Borda misrepresentation of a voter drawn from the population. The paper’s proof appears to extend by replacing each count of top-ranked voters with the corresponding type mass and doing the score comparisons with rational arithmetic. That may be a short extension, but it also gives an algorithm whose dependence is on \(m,\tau,L\), rather than on the potentially enormous population obtained by expanding the rational masses into repeated voters.
So my best case is about research payoff: the first two mirrors are support predicates with no role for population proportions, and the third seems to require little new mathematics. But that does not establish that there is no worthwhile mirror. Theorem 10 passes the basic modeling test, and its compressed high-multiplicity algorithm is relevant to the programme’s stated goals. I cannot honestly defeat that anchor or defend the universal negative; the case against is weak precisely there.
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.