| paper | d4-conf-wine-2017-0009 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-hard to approximate within \(Q^{1-\varepsilon}\) for every fixed \(\varepsilon\in(0,1)\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a rooted binary hierarchy with τ leaf types, binary-rational masses μ_t summing to \(1\), rational hierarchy weights λ, a population scale \(Q\), a seed-mass budget κ, and a target spread ρ, decide whether there are seed masses \(s_t\in[0,μ_t]\) with \(\sum_t s_t\leκ\) such that the threshold-one cascade reaches terminal mass at least ρ.
Start with \(z_t^0=s_t\). At each round, set \(z_t^{r+1}=μ_t\) if \(Q\sum_u λ_{\operatorname{lca}(t,u)}z_u^r\ge1\), and otherwise retain \(z_t^{r+1}=z_t^r\). Choose \(s\) to maximize \(\sum_t z_t^\infty\).
Erol et al. already formulate graphon max-reach over a continuum and reduce finite-type cases to an optimization in τ variables, which narrows the novelty of this formulation; it does not settle the worst-case bit complexity of the proposed mirror. [Erol et al., *Contagion in Graphons*](https://erols.me/files/graphon-contagion-2305.pdf)
fatal: False
The mirror covers the deterministic threshold-one hierarchical-blockmodel InfMax question anchored by Theorem 1. It leaves the stochastic hierarchical-blockmodel results and the 2-quasi-submodular results in Theorems 2–4 aside.
The strongest mirror I believe is a mass version of the paper’s hierarchical-blockmodel InfMax. The paper’s anchor is Theorem 1, proved here by reduction from VertexCover: for every constant \(\varepsilon>0\), InfMax is NP-hard to distinguish between a YES case where some \(k\)-seed set yields \(\sigma(S)=\Theta(N)\), and a NO case where every \(k\)-seed set yields \(\sigma(S)=O(N^\varepsilon)\). This remains true when the graph is a hierarchical blockmodel, the local influence is linear, and every vertex has deterministic threshold \(1\).
Call the mirror Mass-Hierarchical InfMax. An instance has a rooted binary hierarchy with leaf types \(T\), rational type masses \(\mu_t\) summing to \(1\), rational weights \(\lambda\) on hierarchy nodes, a population scale \(Q\), and a rational seed budget \(\kappa\). The interaction coefficient between types \(t,u\) is \(A_{tu}=Q\lambda_{\operatorname{lca}(t,u)}\). A decision is a seed-mass vector \(s\), with \(0\le s_t\le\mu_t\) and \(\sum_t s_t\le\kappa\). Starting from \(z_t^0=s_t\), run the cascade
\[
z_t^{r+1} =
\begin{cases}
\mu_t,&\sum_u A_{tu}z_u^r\ge 1,\\
z_t^r,&\text{otherwise}.
\end{cases}
\]
The question is to choose \(s\) maximizing the final infected mass \(\sum_t z_t^\infty\). A solution is the seed-mass vector and its resulting terminal masses; equivalently, one can ask whether the optimum reaches a specified target. When \(Q\mu_t\) and \(Q\kappa\) are integers, this scaling reproduces the original influence calculation for type-homogeneous finite populations: a type’s infected fraction represents a count divided by \(Q\), and multiplying its mass by \(Q\lambda\) recovers the sum of individual edge weights.
The regime is a large population arranged in nested communities: many residents share a community role, the same threshold, and the same interaction weight to every other role. Think of a broad adoption campaign across provinces and cities, where the question is what fraction of the population can be reached by seeding a fixed fraction. The number of people \(Q\) is large relative to the number of roles \(\tau=|T|\). This is especially natural for Theorem 1’s construction: it uses large repeated bundles and cliques, while its connector roles are comparatively few. The type is the complete block-and-threshold role, not a named person.
This is recognizably the authors’ problem: the seed decision, hierarchical interaction structure, threshold cascade, and spread objective all remain. The co-modification is that interaction from a type scales with its population, so the model uses \(Q\lambda\) against fractional masses. That scaling is what lets the aggregate describe the influence of many residents. The mirror covers Theorem 1 only; I would not infer from it that the stochastic blockmodel results or the paper’s 2-quasi-submodular results have already been continuized.
My expected classification is hardness transfers (Class B). In the paper’s reduction, the VertexCover choices are encoded across hierarchy branches, while large repeated populations amplify the YES/NO gap. That suggests the combinatorics live in the hierarchy and alternatives, not in the ability to name every individual. The continuous prover’s task is to establish that the cover barrier survives mass seeding.
That is also the weakest point in my case. Theorem 1 proves hardness for integer seed sets; Mass-Hierarchical InfMax permits fractional seed mass within a type. The paper’s proof does not show that a fractional allocation cannot spread small amounts across branches and activate a cascade that no discrete seed set could. The threshold-\(1\) clique construction gives some reason to expect an activation barrier—one unit of seed mass can be qualitatively different from less than one—but the necessary gap argument is new. So the theorem is a strong anchor for the mirror, not a proof of its complexity.
The follow-up questions are whether the reduction’s no-case bound holds for arbitrary real seed masses, whether optimal solutions in these instances can be rounded to integer numbers of seeds per role, and whether one-way hierarchical influence admits a tractable mass algorithm even when bidirectional influence remains hard.
The strongest objection to Theorem 1’s mirror is that its proposed mass problem is already very close to an established continuous seeding problem. Erol, Parise and Teytelboym define threshold contagion over a continuum of agents and pose max-reach: choose a seed set of bounded measure to maximize the final infected measure. For finite-type graphons, they reduce the dynamics exactly to an auxiliary network with twice as many nodes as types, then express max-reach as an optimization over the seed mass assigned to each type. A hierarchical interaction matrix is a piecewise-constant, finite-type kernel, so I infer that the proposed Mass-Hierarchical InfMax is largely a reparameterization of that framework. [*Contagion in graphons*](https://erols.me/files/graphon-contagion-2305.pdf), [journal version](https://www.sciencedirect.com/science/article/pii/S0022053123000698).
The match is substantive: both models choose mass by type, let a type’s unseeded members activate together when their threshold is met, and maximize the resulting infected mass. The paper’s absolute threshold can be expressed as a type-specific threshold on the normalized weighted exposure in the graphon model. The graphon work also connects continuum interventions to large sampled networks. So the proposed class-B mirror is not a new continuous formulation waiting to be introduced; its central optimization question already has a continuous model and a finite-type reduction.
That objection has a limit. The graphon paper’s tractability claim is based on reducing the problem to the number of types; it does not give the requested worst-case complexity bound in \(\tau\) and the input bit length. Thus the fractional-seeding hardness question remains open as a complexity question. The cited work makes this a weak case for *no worthwhile mirror*: it is a strong prior-art warning, but the residual complexity analysis could still be worthwhile. And the fractional-seed gap in Theorem 1 is a live proof challenge, not a reason the question lacks meaning.
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.