d4-conf-aaai-2016-0271 (d4-conf-aaai-2016-0271)

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\).

Given a candidate set \(C\) with \(m=|C|\geq 1\), an unlabelled tree \(T\) on \(m\) vertices, and a society \(\mu\) over strict rankings of \(C\), consider the following decision problem.
A society is given by its support: the list of the \(\tau\) distinct types with positive mass, each mass a binary rational, with \(\sum_t\mu(t)=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total binary input length.
For a ranking \(t\), let \(\operatorname{Top}_j(t)\) be its set of top \(j\) candidates. Decide whether there exists a bijection \(\ell:V(T)\to C\) such that \(T[\ell^{-1}(\operatorname{Top}_j(t))]\) is connected for every \(t\in\operatorname{supp}(\mu)\) and every \(j\in\{1,\ldots,m\}\). Singleton induced subtrees are allowed.

Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite lists of strict rankings, this tree-labelling problem is NP-complete even when the input tree has diameter at most four, or maximum degree at most three. [Peters–Elkind (2016)](https://dominik-peters.de/publications/nice-trees.pdf)
A later treatment confirms diameter-four NP-completeness and states the maximum-degree-three extension. [Peters–Yu–Chan–Elkind (2022)](https://dominik-peters.de/publications/spt.pdf) No result explicitly addressing the distribution-input formulation was located.

Result

The decision problem is \(\mathrm{NP}\)-complete. This holds even when the input tree has diameter at most four, and also when its maximum degree is at most three.

The rational-support formulation requires no new hardness theorem: feasibility depends only on which rankings occur, and finite ranking lists can be converted to valid societies in polynomial time.

1. Feasibility depends only on the support

For a bijection \(\ell:V(T)\to C\), let \(P(\ell,t)\) denote the condition that
\[ T[\ell^{-1}(\operatorname{Top}_j(t))] \]
is connected for every \(j\in\{1,\ldots,m\}\).

The acceptance condition is precisely
\[ \exists \ell\ \forall t\in\operatorname{supp}(\mu):P(\ell,t). \]
Thus the numerical values of the positive masses do not affect acceptance. Similarly, repeating a ranking in a finite list does not change the set of feasible labellings.

Consequently, deleting the masses from a society instance and retaining one copy of each supported ranking gives an equivalent finite-list instance in polynomial time. This does not require expanding rational masses into voter multiplicities.

2. Polynomial-time reduction from finite lists

We use the following established theorem: given a finite list of strict rankings over \(C\) and an unlabelled tree on \(|C|\) vertices, deciding whether a bijective labelling makes every top-prefix set connected is \(\mathrm{NP}\)-complete, even for trees of diameter at most four or maximum degree at most three. This is Theorem 8 of [Peters–Elkind (2016)](https://dominik-peters.de/publications/nice-trees.pdf). Their definition of tree single-peakedness is explicitly equivalent to connected top-prefix sets.

Take a source instance with a nonempty list of \(n\) rankings. Remove duplicate rankings, obtaining distinct types \(t_1,\ldots,t_\tau\), where \(1\leq\tau\leq n\). Equality testing and deduplication take polynomial time because the rankings are explicit lists.

Keep \(C\) and \(T\) unchanged. To construct the society, choose
\[ k=\left\lceil\log_2\tau\right\rceil \]
and assign
\[ \mu(t_i)=\frac{1}{2^k}\quad(1\leq i<\tau), \qquad \mu(t_\tau)=\frac{2^k-\tau+1}{2^k}. \]
Assign zero mass to all other rankings, which need not be listed.

These masses satisfy all input requirements:

• They are positive: \(2^k\geq\tau\) implies \(2^k-\tau+1\geq1\).
• Their sum is

\[ \frac{\tau-1+2^k-\tau+1}{2^k}=1. \]

• Each numerator and denominator requires \(O(\log(\tau+1))\) bits. Indeed, the construction uses dyadic rationals, so it also works if “binary rational” means a finite binary expansion.

The additional mass encoding has length \(O(\tau\log(\tau+1))\). Together with the retained rankings, the output therefore has polynomial length in the source input.

For every bijection \(\ell\),
\[ \begin{aligned} \ell\text{ satisfies the source list} &\iff P(\ell,t_i)\text{ holds for every }i\in\{1,\ldots,\tau\}\\ &\iff \ell\text{ satisfies the constructed society}. \end{aligned} \]
The first equivalence follows because duplicate constraints are redundant; the second follows because the constructed support is exactly \(\{t_1,\ldots,t_\tau\}\). Taking existential quantification over \(\ell\) proves that the reduction preserves acceptance.

If an empty source list is permitted, it is always feasible and can be mapped to the fixed yes-instance with one candidate and unit mass.

Since the reduction leaves every nonempty instance’s tree unchanged, it preserves both stated tree restrictions. This proves \(\mathrm{NP}\)-hardness, including those restricted cases.

3. Membership in \(\mathrm{NP}\)

A certificate lists the candidate assigned to each input vertex. Its length is \(O(m\log(m+1))\) bits after indexing candidates. The verifier first checks that this assignment is a bijection.

For each of the \(\tau\) supported rankings and each \(j\in\{1,\ldots,m\}\), it marks the vertices corresponding to the top \(j\) candidates and performs a graph search restricted to marked vertices. It accepts that prefix exactly when all marked vertices are reached.

A tree has \(m-1\) edges, so each search uses \(O(m)\) graph operations. All prefix checks therefore use \(O(\tau m^2)\) graph operations, with polynomial bit complexity. Singleton prefixes pass automatically.

The masses play no role in these checks. If input validity must also be verified, positivity and normalization of binary rationals can be checked in polynomial time in \(L\): a product of their denominators has bit length at most the sum of their denominator bit lengths, hence \(O(L)\), and supplies a common denominator for exact summation.

Thus the problem belongs to \(\mathrm{NP}\).

4. Conclusion

The polynomial reduction and certificate verifier prove \(\mathrm{NP}\)-completeness. A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\). An additional theorem specifically formulated for distributions is unnecessary.

⟨structured verdict parsed — rendered above⟩

The prover’s output resolves the task correctly. The support encoding preserves the finite-list feasibility problem, the reduction has polynomial size, and the certificate verifier establishes membership in \(\mathrm{NP}\). No major or minor mathematical issues were found.

1. The cited hardness theorem applies

Theorem 8 of [Peters–Elkind (2016)](https://dominik-peters.de/publications/nice-trees.pdf) states precisely the required finite-list result: SINGLE-PEAKED TREE LABELLING is \(\mathrm{NP}\)-complete even for input trees of diameter at most four or maximum degree at most three. Its input consists of a profile of strict rankings and an unlabelled tree with as many vertices as candidates.

The same paper’s preliminaries explicitly identify tree single-peakedness with the requirement that every nonempty top-prefix set induce a subtree. Because the ambient graph is a tree, this is exactly the connected-induced-subgraph condition in USER_TASK.

Thus the prover cites the correct theorem, and its hypotheses match the source problem used in the reduction. The two tree restrictions are separate hardness statements; the prover does not claim hardness when both restrictions hold simultaneously.

2. Support invariance is exact

The predicate \(P(\ell,t)\) includes every required prefix length \(j\in\{1,\ldots,m\}\). The acceptance condition
\[ \exists\ell\ \forall t\in\operatorname{supp}(\mu):P(\ell,t) \]
correctly reproduces USER_TASK.

Positive mass values do not appear in this condition. Consequently:

• Changing positive masses without changing the support preserves acceptance.
• Repeated occurrences of a ranking impose identical constraints and can be removed.
• Discarding the masses produces an equivalent finite-list instance without expanding voter multiplicities.

These statements hold for every candidate labelling, so they also hold after existential quantification over labellings.

3. The reduction produces a valid, polynomial-size society

Deduplication is polynomial because each source ranking is explicitly represented. For a nonempty source list, the resulting support size satisfies \(1\leq\tau\leq n\).

With \(k=\lceil\log_2\tau\rceil\), the proposed masses are valid:

• The first \(\tau-1\) masses are positive.
• The last numerator \(2^k-\tau+1\) is at least one.
• Their sum is exactly

\[ \frac{\tau-1+2^k-\tau+1}{2^k}=1. \]

The boundary case \(\tau=1\) is covered: \(k=0\), the first assignment has no indices, and the sole mass is one.

Each numerator and denominator has \(O(\log(\tau+1))\) bits. The dyadic construction also satisfies the interpretation of “binary rational” as a finite binary expansion. The additional encoding length \(O(\tau\log(\tau+1))\) is polynomial in the explicit source input length.

The constructed support is exactly the deduplicated source list. Both displayed acceptance equivalences therefore hold in both directions for every bijection \(\ell\). No numerical approximation or implicit enumeration of unsupported rankings is involved.

The empty-list case is correctly handled by a fixed yes-instance. Its one-vertex tree satisfies both tree restrictions. For nonempty lists, the tree is unchanged, so each restricted hardness result transfers.

4. The certificate verifier is polynomial and correct

After indexing candidates, a certificate assigning a candidate to each vertex has length \(O(m\log(m+1))\). Checking bijectivity ensures that it represents precisely an admissible labelling.

For each supported ranking and prefix length, a graph search within the marked vertices determines whether the induced subgraph is connected. Every prefix is nonempty, so a search can start at a marked vertex.

There are \(\tau m\) prefix checks. Each marking and search requires \(O(m)\) graph operations on a tree, yielding the stated \(O(\tau m^2)\) bound. The cases \(j=1\), \(j=m\), and \(m=1\) are all covered.

The optional rational-validity argument is also sound: the product of explicitly encoded positive denominators has bit length \(O(L)\), allowing exact normalization checks with polynomial-time integer arithmetic.

5. Adjudication and repair feedback

The reduction proves \(\mathrm{NP}\)-hardness, and the verifier proves membership in \(\mathrm{NP}\). Together they establish the claimed \(\mathrm{NP}\)-completeness, including each stated tree restriction.

No additional clarification, missing lemma, or proof repair is needed.

⟨structured verdict parsed — rendered above⟩