| paper | d4-journals-jair-2011-0040 |
| 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, hence \(\mathrm{NP}\)-hard; in \(\mathrm P\) if and only if \(\mathrm P=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a variable set \(\mathbf V\), state cardinalities \(r\), a finite support \(\mathcal T\) of DAG types with positive rational masses \(\mu_G\) summing to \(1\), and a positive integer \(d\), does there exist a DAG \(H\) over \(\mathbf V\) such that \(I(H)\subseteq\bigcap_{G\in\mathcal T}I(G)\) and \(\kappa_r(H)\le d\), where \(\kappa_r(H)=\sum_{B\in\mathbf V}\left(\prod_{A\in Pa_H(B)}r_A\right)(r_B-1)\)?
A population of institutions submitting DAG structures over a shared variable schema, represented by a distribution \(\mu\) over DAG types. The decision variable is a consensus DAG \(H\); require it to assert only independences shared by every type in \(\operatorname{supp}(\mu)\), and minimize its parameter count \(\kappa_r(H)\).
Once the positive support is fixed, changing mass values cannot change feasibility, so the problem reduces computationally to a finite set of DAG types; the proponent acknowledges this limitation but does not make the mirror mass-sensitive.
fatal: False
Covers Theorem 3's NP-completeness result for minimum-parameter unanimous consensus; leaves Theorem 1's nonuniqueness result, Theorem 4's ordering-conditioned characterization, and Theorem 5 and Corollary 1's MDI-map and transformation results outside the mirror.
The strongest positive case is a population of model-producing sites, not a continuum of Bayesian networks. Imagine a large consortium in which many hospitals or agencies use the same variable schema, state cardinalities, and modeling protocols. Each site submits a BN structure. Standardized workflows could produce many repeated structures, so the number \(N\) of submissions may be much larger than the number \(\tau\) of distinct structures. A type is one submitted DAG over the shared variables; its mass is the fraction of sites submitting it. The desired output remains one consensus DAG.
Call the decision problem \(\textsc{Consensus}_\infty\). Its input is a variable set \(\mathbf V\), a shared state-cardinality vector \(r\), a finite support \(\mathcal T\) of DAG types with positive rational masses \(\mu_G\) summing to \(1\), and a positive integer \(d\). Define \(\kappa_r(H)=\sum_{B\in\mathbf V}\left(\prod_{A\in Pa_H(B)}r_A\right)(r_B-1)\). The question is whether there exists a DAG \(H\) over \(\mathbf V\) such that \(I(H)\subseteq\bigcap_{G\in\mathcal T}I(G)\) and \(\kappa_r(H)\le d\). A solution is such a DAG \(H\); the corresponding optimization problem minimizes \(\kappa_r(H)\). This preserves the paper’s unanimity requirement: the consensus may assert only independences shared by every positive-mass type.
My lead anchor is Theorem 3, proved in this paper: given a set of DAGs \(G^1,\ldots,G^m\) over \(\mathbf V\) and a positive integer \(d\), deciding whether there exists a DAG \(G\) over \(\mathbf V\) with \(I(G)\subseteq\bigcap_{i=1}^m I(G^i)\) and at most \(d\) associated parameters is NP-complete. The paper proves membership in NP by giving a polynomial verification procedure. Its hardness proof builds on the degree-bounded Feedback Arc Set to LEARN reduction cited from Chickering et al. (2004), then supplies its own reduction from LEARN to CONSENSUS.
The authors should recognize this as their consensus problem with repeated submissions represented by a distribution over graph types. Given any original instance, assign positive masses to its DAGs; the feasible consensus DAGs and parameter counts are unchanged. In particular, the paper’s hardness construction uses three input DAGs, so the mirror remains NP-hard with \(\tau=3\) and the prescribed state cardinalities in that reduction. Replicating each type to form a much larger population does not remove that hardness. I expect hardness transfers (Class B): the reduction’s combinatorics lie in the graph and variable structure, not in the number of individual submitters. The mirror covers the paper’s NP-completeness result about selecting a minimum-parameter consensus; it does not attempt to continuize the later ordering heuristic or the combination of consensus parameters.
This mirror also generates concrete follow-ups: does hardness persist with only two types, arbitrary state cardinalities, or bounded in-degree? What are the parameterized and approximation complexities in \(\tau\), \(|\mathbf V|\), and the cardinalities? A threshold allowing a small mass of dissenting types would be a separate, less direct extension.
The weak point is that the masses have no effect beyond determining which types occur: because the paper requires unanimity, a type with tiny positive mass constrains the consensus just as much as one with mass \(1/2\). So this is a genuine continuous-population instance regime, but not a fractional relaxation that changes the optimization or promises a tractability gain. I think that limitation is acceptable here: the paper’s own criterion is unanimous, and a large population grouped into repeated graph types is a sensible regime for applying that criterion.
Theorem 3 is a real computational anchor. The strongest mirror is a population of institutions that submit Bayesian network structures over a shared variable schema. Let each type be a DAG \(G\), and require a consensus DAG \(H\) to satisfy \(I(H)\subseteq I(G)\) for every type with positive mass, while minimizing the paper’s parameter count. That is a clean formulation, and the paper’s finite instances embed in it by assigning positive masses to their input DAGs.
But this formulation exposes the central problem: the consensus criterion uses only the support of \(\mu\), not its masses. A type with mass \(10^{-12}\) constrains \(H\) just as much as one with mass \(1/2\). Replicating submissions or changing their proportions has no effect until a type’s mass reaches zero, at which point the constraint disappears. Thus the distribution reduces to a finite set of distinct DAGs. The objection is not that the continuous version has the same complexity answer; it is that population size and composition do no work in the problem’s semantics. Even the reduction using three input DAGs illustrates this: arbitrarily many institutions assigned to those three types still supply the same three constraints.
A more realistic story about many sites does not make the masses relevant under the paper’s rule. Repeated copies of a DAG add no agreement, while accounting for provenance or reliability would require changing the problem. One could make mass matter by permitting some mass of dissenting types or weighting disagreements, but that replaces unanimous consensus with a different objective. It may be a worthwhile project, but it is not a stronger mirror of Theorem 3.
This is a case against spending ChoCo’s continuization effort here, not an airtight proof that no useful scenario exists. A population of model producers with support-based unanimity is coherent, and the authors might recognize it as their problem. The negative case is that it remains a finite set-consensus problem written in distribution notation; the proposed mirror does not give the population a meaningful computational role.
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.