| paper | d4-conf-atal-2016-0057 |
| 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: \(\mathrm{NP}\)-hard; a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given a finite type set (\Theta ), rational masses (\mu_i ) summing to \(1\), nonnegative rational contact intensities (a_{ij} ), and a rational intervention budget (\beta ), choose rational intervention masses (x_i\in[0,\mu_i] ) with (\sum_i x_i\le\beta ). Set (y_j^{(0)}=x_j ) and (y_j^{(1)}=y_j^{(0)}+(\mu_j-y_j^{(0)})(1-\exp(-\sum_i a_{ij}y_i^{(0)})) ). For rational (\varepsilon>0 ), compute a feasible allocation whose total influenced mass (\sum_j y_j^{(1)} ) is within (\varepsilon ) of the maximum.
A one-intervention influence-maximization problem over a finite distribution of complete contact-profile types: (\mu_i ) is type mass, (a_{ij} ) gives type-level contact intensity, (x_i ) is intervention mass, and the objective is total influenced mass after one diffusion round.
The contact matrix removes sparse local neighborhoods and their overlaps, and the proposed national-program scenario does not establish that the paper’s target population has the exchangeable contact patterns this model assumes.
fatal: False
The mirror covers Theorem 5.2’s one-intervention influence-maximization core; it leaves aside Theorem 5.1’s full-information approximation result, Theorem 5.3’s adaptivity result, and HEAL’s algorithms and experiments.
The strongest mirror is the one intervention case at the heart of the paper’s hardness result. Theorem 5.2, proved in this paper using the cited NP-hardness of standard influence maximization, says that DIME is NP-hard. Its proof sets \(E_u=\varnothing\), \(T=1\), \(L=1\), and \(p(e)=1\) for every edge, reducing DIME to standard influence maximization. That is a useful anchor because it isolates the underlying task—choosing intervention participants to maximize influence—without relying on DIME’s sequential adaptation or uncertain edges.
I would mirror it with Continuous Typed Influence Maximization. An instance has a finite set of types \(\Theta\), rational type masses \(\mu_i\) summing to \(1\), a rational budget \(\beta\), a diffusion horizon \(H\), and a matrix of nonnegative rational contact intensities \(a_{ij}\). Type \(i\) means a group whose members share the intervention-relevant characteristics and the same contact propensities with every type. The intensity \(a_{ij}\) gives the rate at which informed mass of type \(i\) reaches each susceptible member of type \(j\).
Choose intervention masses \(x_i\), with \(0\le x_i\le\mu_i\) and \(\sum_i x_i\le\beta\). Starting from \(y_i^{(0)}=x_i\), let spread evolve by \(y_j^{(r+1)}=y_j^{(r)}+(\mu_j-y_j^{(r)})(1-\exp(-\sum_i a_{ij}y_i^{(r)}))\). Here \(y_j^{(r)}\) is the informed mass of type \(j\) after diffusion round \(r\); the exponential term represents the chance a susceptible person receives no successful contact. The objective is to maximize \(\sum_j y_j^{(H)}\). A computational version asks, given \(\varepsilon>0\), for a feasible rational allocation \(x\) whose final influenced mass is within \(\varepsilon\) of the optimum. For the anchor, take one intervention and the corresponding one-step spread, with no uncertain network state.
A plausible regime is a regional or national prevention programme serving many thousands of youth, with dozens or hundreds of modeled types—such as combinations of service catchment, age band, and contact profile—and many people in each type. The intervention question is then naturally stated as “what share of each group should we reach?” rather than “which named individuals should we select?” The contact matrix replaces an identity-level friendship graph with type-specific mixing rates. That is a consequential co-modification, but it follows from treating large groups as exchangeable while retaining influence spread as the goal. I think the DIME authors could recognize this as their participant-selection problem in a population model.
My prior is that this is a Class C candidate: when the number of types is part of the input, optimizing a nonlinear cascade over fractional allocations may still be hard for reasons specific to the continuous model. I would not claim that Theorem 5.2’s NP-hardness transfers. Its proof uses an arbitrary discrete graph, while this mirror replaces that topology with a type interaction matrix and permits divisible seed allocations. The actual research question is whether this problem admits useful convex structure or approximation algorithms, or whether its hardness persists as the type set grows.
The scope is deliberately narrow: it mirrors Theorem 5.2’s uncertainty-free, one-intervention influence-maximization core. It does not mirror DIME’s adaptive policies, learning from observed neighborhoods, or HEAL’s algorithms and experiments. Those lead to further questions: how does hardness change with \(\tau=|\Theta|\); can finite stochastic block populations be approximated by this mass model with useful error bounds; and what happens when interventions reveal aggregate contact data and future allocations adapt to it?
The weak point is that the mirror smooths away individual network structure, including unusual high-impact people and correlated neighborhoods—the features that make DIME’s graph partitioning and sequential observation valuable. So this is not a claim that DIME itself already has a mean-field formulation. It is a credible population regime for the paper’s central influence-maximization question, and a precise place to ask whether the discrete hardness in Theorem 5.2 survives continuization.
Theorem 5.2 is a real computational anchor: it asserts NP-hardness of the optimization problem. The cleanest mirror is its one-intervention, known-network case, so the absence of sequential adaptation or uncertain edges cannot dispose of it.
The difficulty is that the proposed type interaction matrix is not a sufficient description of the networks in this paper. Influence depends on which people share neighbors and how those neighborhoods overlap. The paper itself says degree centrality performs poorly because it misses overlap between influential people. Two networks can have the same type masses and average contact rates while giving very different rewards for the same seed choices. To preserve those distinctions, a type would need to encode much of each person’s network position. In the paper’s sparse networks, that can leave nearly every person as a separate type. Grouping people by broad categories and retaining only average rates restores multiplicity by replacing the graph with an exchangeable mixing model.
That replacement is coherent as a mean-field intervention problem, but it is a weak mirror of this paper’s result. The paper selects participants from an observed friendship network because their particular positions drive spread. Its networks have only a few hundred edges for roughly 150–170 people, and its artificial networks have bounded degree. A dense mixing model assumes contact patterns the paper does not posit. A dense graphon limit would also lose the paper’s sparse structure; a sparse limit would need to retain local neighborhoods and their overlap, bringing back the problem of how to represent the relevant participant distinctions. Scaling the intervention budget to a positive share of the population could make a mass-allocation question meaningful, but that adds a new intervention regime alongside the new mixing model.
So the strongest negative case is about fidelity: the mirror either retains enough network structure that the high-multiplicity compression may disappear, or gains a compact type model by assuming away the topology that makes this paper’s participant-selection problem distinctive. A national programme with genuinely exchangeable groups could still motivate the proposed optimization, and the authors might recognize it as a related problem. I cannot honestly rule that out. The negative case is therefore strongest for the paper’s own sparse-network setting, and weak as a universal claim that no worthwhile continuous mirror exists.
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.