d4-conf-ijcai-2019-0952 (d4-conf-ijcai-2019-0952)

Given \(m\) candidates and an explicit rational distribution \(\mu\) over complete rankings, promised to equal the uniform distribution \(U(T)\) over rankings single-peaked on a unique labeled tree \(T\), output \(T\).

Let \(C=\{1,\ldots,m\}\), with \(m\geq1\). Rankings are strict total orders. A ranking is single-peaked on an undirected tree \(T\) with vertex set \(C\) if each nonempty initial segment induces a connected subgraph of \(T\). Let \(S(T)\) contain all such rankings, and let \(U(T)\) assign mass \(1/|S(T)|\) to each of them and zero elsewhere.
A society is given by its support: the list of the \(\tau\) distinct rankings with positive mass, each mass a binary rational, with masses summing to \(1\). Here \(\tau\) is the support size, not the number \(m!\) of possible rankings; \(L\) is the total input bit length.
The input distribution \(\mu\) is promised to equal \(U(T)\) for exactly one labeled tree \(T\). The reconstruction problem outputs the edge set of \(T\); no behavior is prescribed outside the promise.

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

For finite samples, a polynomial-time procedure recovers the generating tree with probability at least \(1-\delta\) from \(2m\alpha\) independent samples from \(U(T)\), where \(0<\delta<1\) and \(\alpha\geq2\ln m+\ln(1/\delta)\). [Source](https://www.ijcai.org/proceedings/2019/0082.pdf)
No result settling exact reconstruction from an explicitly listed distribution was located in the literature search.

1. Result

The promised reconstruction problem is solvable in deterministic polynomial time. For \(m\geq 2\), the tree’s edges are exactly the unordered pairs appearing in the first two positions of a listed ranking.

The proof also shows that the uniqueness promise is redundant: the full support determines the labeled tree.

2. Structural lemma

Write a ranking as \(r=(r_1,\ldots,r_m)\), from highest to lowest preference.

Lemma. For any tree \(T\) on \(C\), with \(m\geq 2\),
\[ E(T)=\bigl\{\{r_1,r_2\}:r\in S(T)\bigr\}. \]

Proof. We prove both inclusions.

First, let \(r\in S(T)\). By definition, its two-vertex initial segment \(\{r_1,r_2\}\) induces a connected subgraph of \(T\). A graph induced by two distinct vertices is connected precisely when they are adjacent. Therefore \(\{r_1,r_2\}\in E(T)\).

Conversely, fix an edge \(\{x,y\}\in E(T)\). Begin a ranking with \(x,y\). This initial segment induces a connected subgraph.

Suppose we have constructed an initial segment whose vertex set \(A\) induces a connected subgraph, and \(A\neq C\). Because \(T\) is connected and \(A\) is nonempty and proper, an edge joins some vertex of \(A\) to some vertex \(z\in C\setminus A\). Indeed, if no such edge existed, there would be no path from \(A\) to its complement, contradicting connectivity. Append \(z\). The induced subgraph on \(A\cup\{z\}\) is connected, since it contains the connected subgraph on \(A\) and an edge joining \(z\) to that subgraph.

Repeating this step produces a strict total order of all vertices. Its singleton initial segment is connected, its two-vertex initial segment is connected, and every subsequent initial segment is connected by construction. Thus the resulting ranking belongs to \(S(T)\) and begins with \(x,y\). This proves the reverse inclusion. \(\square\)

3. Algorithm and correctness

Let \(R\) be the explicitly listed support of \(\mu\).

• If \(m=1\), output the empty edge set.
• Otherwise, for each \(r\in R\), record the pair \((\min\{r_1,r_2\},\max\{r_1,r_2\})\).
• Sort these pairs, remove duplicates, and output the corresponding unordered edges.

Under the promise \(\mu=U(T)\), every ranking in \(S(T)\) has positive mass, and every ranking outside \(S(T)\) has zero mass. Since the input lists the entire positive support, \(R=S(T)\). The lemma therefore proves that the algorithm outputs exactly \(E(T)\). For \(m=1\), the unique tree has no edges, so the first step is also correct.

The numerical masses need not be used. Moreover, if \(U(T)=U(T')\), their supports coincide, so the lemma gives \(E(T)=E(T')\). Hence the generating labeled tree is necessarily unique.

4. Running time and relation to sampling

Reading the input takes \(O(L)\) bit operations. Each vertex label uses \(O(\log(m+1))\) bits. Deterministic comparison sorting of the \(\tau\) recorded pairs, followed by duplicate removal, takes \(O(\tau\log(\tau+1)\log(m+1))\) bit operations. Thus the total running time is
\[ O\bigl(L+\tau\log(\tau+1)\log(m+1)\bigr), \]
which is polynomial in \(m,\tau,L\).

This argument uses the entire support. A finite sample can omit rankings witnessing an edge, so the sample-recovery question in the [cited paper](https://www.ijcai.org/proceedings/2019/0082.pdf) requires additional analysis.

⟨structured verdict parsed — rendered above⟩

Verification report

The argument is correct and resolves the promised reconstruction problem in deterministic polynomial time. No mathematical or complexity gaps were found.

1. Structural lemma: forward inclusion

For \(m\geq 2\), every ranking \(r\in S(T)\) has a connected two-vertex initial segment. Because rankings are strict, \(r_1\neq r_2\). The induced subgraph on these two vertices is connected exactly when they are adjacent. Thus every recorded pair belongs to \(E(T)\).

This inclusion is fully justified.

2. Structural lemma: reverse inclusion

The construction starts with the endpoints \(x,y\) of an arbitrary edge, so its first two prefixes are connected.

At every subsequent step, the current vertex set \(A\) is nonempty, proper, and connected. Connectivity of \(T\) guarantees an edge from \(A\) to its complement, exactly as the prover explains. Appending the outside endpoint preserves connectivity of the induced subgraph.

Each appended vertex is new, and each step increases the prefix size by one. Consequently, the process terminates with a strict total order containing every vertex. All its nonempty prefixes are connected. This supplies a ranking in \(S(T)\) witnessing the chosen edge.

The reverse inclusion and hence the lemma are fully proved, including the case \(m=2\), where no extension is needed.

3. Identification of the listed support

Under the promise \(\mu=U(T)\), each ranking in \(S(T)\) has positive mass and every other ranking has zero mass. The input explicitly lists the entire positive support, so \(R=S(T)\).

This step correctly uses the support specification; it does not assume that a finite sample contains every ranking.

4. Algorithm and edge cases

For \(m\geq2\), the algorithm records exactly the pairs described by the lemma. Sorting and removing duplicates therefore returns exactly \(E(T)\).

For \(m=1\), the sole labeled tree has an empty edge set, which the algorithm returns. Ignoring the numerical masses is valid because correctness is required only under the promise.

5. Uniqueness claim

Equality of the distributions implies equality of their positive supports. For \(m\geq2\), the lemma then gives equality of the edge sets. For \(m=1\), uniqueness holds directly.

Thus the additional claim that the uniqueness promise is redundant is also correct.

6. Running time and sampling distinction

Each recorded pair contains two labels of \(O(\log(m+1))\) bits. Comparison sorting uses \(O(\tau\log(\tau+1))\) comparisons, each costing \(O(\log(m+1))\) bit operations. Pair extraction, duplicate removal, and output fit within the stated bound together with the \(O(L)\) input scan.

The resulting bound
\(O(L+\tau\log(\tau+1)\log(m+1))\)
is polynomial in the requested parameters. The possible size of the full support does not invalidate this conclusion: \(\tau\) is explicitly an input-size parameter.

The final sampling observation accurately identifies the limitation of applying this argument to samples. The proof does not rely on the cited sampling theorem.

Repair feedback: None required.

⟨structured verdict parsed — rendered above⟩