| paper | d4-conf-sagt-2020-0020 |
| 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}\)-complete under polynomial-time many-one reductions; polynomial-time solvable if and only if \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2.1
statement extracted from the paper’s text layer
Given a fixed candidate set \(C\) and a finite-support distribution \(\mu\) over complete rankings of \(C\), find a connected graph \(G=(C,E)\) minimizing \(|E|\), subject to every ranking \(t\) with \(\mu_t>0\) having each of its prefixes induce a connected subgraph of \(G\).
Types are complete rankings \(t\) of the fixed candidates \(C\), with rational masses \(\mu_t\) summing to \(1\). The decision variables are binary edge indicators for \(G\); minimize their sum while requiring every positive-mass type to be a traversal of \(G\).
The mirror covers the minimum-edge and minimum-maximum-degree hardness results, Theorems 2.1 and 2.2. It leaves the tree, path, and pseudotree recognition results, as well as the experiments, aside.
The strongest honest case is a Class B mirror: continuize the population while keeping the paper’s exact requirement that every preference be explained by one sparse candidate graph. It gives a well-defined high-multiplicity problem, but it does not make these two optimization problems easier.
A type is a complete ranking \(t\) of the fixed candidate set \(C\). The society is a finite-support distribution \(\mu\), with positive rational mass \(\mu_t\) on each of its \(\tau\) observed ranking types. For the lead problem, Minimum-Edge Graph Compatibility\(_\infty\), the instance is \((C,\mu)\); the task is to output a connected graph \(G=(C,E)\) with as few edges as possible, subject to every positive-mass type being a traversal of \(G\). Equivalently, for every \(t\in\operatorname{supp}(\mu)\) and every prefix length \(r\), the vertices in the first \(r\) positions of \(t\) induce a connected subgraph of \(G\). An optimum graph is a solution. This is the paper’s underlying graph problem, not a continuous graph encoding.
The regime is a large electorate ranking a fixed slate of alternatives: for example, a high-turnout ranked election with a modest number \(m\) of candidates. Voters with the same complete ballot are one type; the electorate may have \(N\gg\tau\) voters, with mass \(\mu_t\) recording each type’s population share. This is a regime claim, not a claim about all elections: if nearly every ballot is distinct, the high-multiplicity rationale is weaker. The graph also has the paper’s stated interpretation in recommendation settings: a sparse compatible graph summarizes which alternatives are close in the preference data.
The lead anchor is Theorem 2.1, proved in this paper: “Given a preference profile \(\mathcal{P}\), it is NP-hard to find a graph compatible with \(\mathcal{P}\) with a minimum number of edges.” The authors reduce from Set Cover. Their construction forces the set-vertices to form a clique; an edge from a set-vertex to a special vertex \(z\) represents selecting that set. A voter for each universe element requires \(z\) to connect to at least one set containing that element. Thus a compatible graph with \(\binom{m}{2}+k\) edges exists exactly when the Set Cover instance has a cover of size \(k\). The reduction’s combinatorics live in the candidate set and the set-cover choices, so this is a natural hardness-transfer anchor.
A second, independently meaningful anchor is Theorem 2.2, also proved here: finding a compatible graph with minimum maximum vertex degree is NP-hard. Its Set Cover construction again uses set-vertices and \(z\), with auxiliary vertices forcing \(z\) to have a baseline degree of \(m\). Edges from \(z\) to set-vertices encode the chosen sets, and the degree bound \(m+k\) limits the choices to at most \(k\); compatibility requires those choices to cover the universe. The resulting continuous question, Minimum-Max-Degree Graph Compatibility\(_\infty\), has the same input and traversal constraints as the lead problem, but asks for a compatible graph minimizing \(\Delta(G)\). I consider Theorem 2.1 the stronger anchor: minimizing edges is the paper’s central sparsity objective, and its reduction is stated in more detail. The degree result is worth including because it establishes hardness for the paper’s second stated objective as well.
Both mirrors inherit the paper’s NP-hardness. A finite profile becomes an empirical distribution by assigning each voter’s ranking mass \(1/N\), combining duplicate rankings. Compatibility depends only on whether a ranking has positive mass, so the feasible graphs and both objectives are unchanged. Conversely, for these exact problems the weights can be ignored once the support is known: one voter per support type imposes the same constraints. This also means hardness persists in a high-multiplicity regime: replicate each support type equally many times, making \(N/\tau\) arbitrarily large without changing the instance’s answer. The expected classification is hardness transfers (Class B), not continuum-specific hardness.
The authors should recognize these as their problems: the paper asks for a graph on which every preference is a traversal, optimizing precisely the number of edges or the maximum degree. Replacing the voter list by its distribution over complete rankings preserves that question exactly. The mirror covers those two universal-compatibility optimization results; it does not claim to continuize the paper’s outcome space or its recognition results for trees, paths, or pseudotrees.
My weakest point is also the limit of the positive case: mass shares do not affect either optimization problem beyond distinguishing zero mass from positive mass. The continuous formulation is faithful and sensible for a large electorate, but it reveals no new mass-sensitive structure or tractability. The paper’s set-cover reductions explain why: the hard choices concern the candidate graph. A further, distinct question—closer to the paper’s future direction of maximum-likelihood graph learning—is to minimize graph size while requiring at least \(1-\varepsilon\) of the population’s mass to have rankings compatible with the graph. That would make the masses computationally consequential, but it relaxes the paper’s exact compatibility condition, so I would not use it as an anchor for the main mirror.
The strongest case against these anchors is that their exact continuous versions use the society’s support but discard its masses. Let \(S=\operatorname{supp}(\mu)\). For either objective, the feasible graphs are exactly those compatible with every ranking in \(S\). Replacing \(\mu\) by a profile with one voter of each type leaves the feasible graphs and optimum unchanged. Replicating those voters, or changing their positive masses without changing \(S\), also changes nothing.
That makes the mirrors of Theorem 2.1 (minimum number of edges) and Theorem 2.2 (minimum maximum degree) mathematically faithful but thin as continuizations. The paper’s ILP already has candidate-edge variables and one constraint family per ranking prefix; repeated voters merely duplicate constraints. In the exact mirror, even a type with vanishingly small positive mass constrains the graph as much as every other type. The distribution therefore acts only as a support set, with a discontinuous effect when a new type enters or leaves it. This is a real limit on the scientific payoff: neither theorem becomes a mass-sensitive population computation, and no new continuous-optimization structure appears.
The degree objective does not escape that objection. It changes what is optimized over the same support-defined feasible set; it does not make population masses computationally active. These are two valid named computational anchors, but their exact mirrors share the same support-only collapse.
The trouble for a *universal* negative case is the stronger, mass-sensitive version. One could minimize \(|E(G)|\), or \(\Delta(G)\), subject to \(G\) explaining at least a \(q\)-fraction of the population’s mass. Then rare ranking types need not veto a graph, while common types matter more. That changes the paper’s exact compatibility predicate, but its authors explicitly propose relaxing perfect compatibility and learning a graph from the observed preferences. This is an author-recognizable extension, and its computational complexity is a plausible question about a continuous population.
One can argue that this threshold version remains a weighted discrete graph-selection problem, rather than opening a new LP or pricing toolbox. That limits the case for its payoff, but does not establish that the problem is uninteresting. Large electorates with many repeated ballots are a sensible high-multiplicity regime, so lack of multiplicity is not a sound objection either.
My honest negative case is therefore narrow: the two exact mirrors are support encodings with little mass-sensitive content. I cannot make a convincing case that no worthwhile continuous mirror exists in any scenario; the paper’s own proposed imperfect-fit direction leaves a credible one.
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.