| paper | d4-conf-wine-2017-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard even when \(1/\varepsilon=O(L)\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(\mathcal{T}\), rational masses \(\mu_t\) summing to \(1\), rational contact weights \(W_{tu}\), nondecreasing piecewise-linear response functions \(\phi_t\), a seed share \(\alpha\), and an accuracy \(\varepsilon\), compute seed masses \(s_t\in[0,\mu_t]\) with \(\sum_t s_t=\alpha\) whose final infected mass is within additive \(\varepsilon\) of optimal. Define \(q_t^{(0)}=s_t\) and \(q_t^{(r+1)}=s_t+(\mu_t-s_t)\phi_t\!\left(\frac{\sum_u W_{tu}q_u^{(r)}}{\sum_u W_{tu}\mu_u}\right)\), using exposure \(0\) for a zero denominator and requiring \(\phi_t(0)=0\); maximize \(\sum_t q_t^{\infty}\). What is the exact or approximation complexity in \(|\mathcal{T}|\), the response descriptions, input bit length, and \(\varepsilon\)?
A continuum population with finitely many exchangeable contact and response types, each carrying mass \(\mu_t\). Choose seed mass \(s_t\) per type under total budget \(\alpha\), evolve infected masses by the type-level threshold-response recurrence, and maximize final infected mass.
The opponent’s strongest point is that infected shares by type discard neighborhood overlap and local correlations, and the case does not show that its aggregate recurrence is a limit of a nontrivial family of the paper’s graph cascades.
fatal: False
The mirror covers fixed-budget seed placement and the oracle-based computational focus of Theorem 1. It leaves aside Theorem 2’s graph-specific comparison with greedy, the empirical network results, hierarchical-decomposition comparisons, and the message-passing algorithm.
The strongest honest mirror is type-level continuous influence maximization for a large population organized into repeated network roles. Imagine a national product-adoption campaign or public-health intervention with millions of people but a modest number \(\tau\) of behavioral and community segments. People in a type share the same contact profile across segments, the same cascade response, and the same seed eligibility. The decision is naturally stated as “reach an \(\alpha\) fraction of the population,” rather than “pick exactly \(k\) named people.”
My lead anchor is Theorem 1, proved in this paper. It states that for a graph \(G=(V,E)\) with \(n=|V|\) vertices and \(m=|E|\) edges, fixed positive integers \(k,r\), and a hierarchical decomposition \(T\), DPIM makes \(O(nk^2)\) calls to the global-influence oracle \(\sigma(\cdot)\). This is the paper’s named algorithmic result; it does not give a named hardness classification. It is also an oracle-query bound, not by itself a polynomial-time result in the standard model: computing \(\sigma\) may take substantial work.
Here is the continuous problem I would hand to a prover. Call it \(\varepsilon\)-Type-Level Continuum Influence Maximization. An instance has a finite type set \(T\), rational type masses \(\mu_t\ge 0\) summing to \(1\), a rational contact matrix \(W_{tu}\), nondecreasing rational piecewise-linear response functions \(\phi_t:[0,1]\to[0,1]\), a rational seed share \(\alpha\), and an accuracy \(\varepsilon>0\). For type \(t\), \(W_{tu}\) describes its contact weight toward type \(u\); \(\phi_t\) gives the activation probability induced by the infected share of its contacts. A hierarchy over types may also be supplied to mirror DPIM’s decomposition input.
A solution is a seed-mass vector \(s\) with \(0\le s_t\le\mu_t\) and \(\sum_t s_t=\alpha\), whose expected final spread is within additive \(\varepsilon\) of the best feasible spread. More explicitly, let \(q_t^{(0)}=s_t\), let
\[
z_t(q)=\frac{\sum_u W_{tu}q_u}{\sum_u W_{tu}\mu_u},
\]
and iterate
\[
q_t^{(r+1)}=s_t+(\mu_t-s_t)\phi_t\!\left(z_t(q^{(r)})\right).
\]
For a zero denominator, set \(z_t=0\) and require \(\phi_t(0)=0\). The limit \(q^\infty\) is the infected mass by type. This is the aggregate threshold cascade: thresholds are drawn uniformly as in the paper, seeds are chosen before those draws, and the mass of nonseed agents whose thresholds have been crossed is represented directly. The objective is to maximize \(\sum_t q_t^\infty\).
The computational question is whether this problem admits an exact or additive-approximation algorithm whose running time is controlled by \(\tau\), the response-function description, the input bit length, and \(\varepsilon\), rather than by the number of people represented. That is the connection to Theorem 1: it studies the same underlying choice—where to place a fixed intervention budget to maximize cascade spread—while replacing choices among individual nodes with choices of mass across types. The theorem does not already solve this continuous problem; it motivates asking whether hierarchical allocation and influence-oracle methods can be carried over without enumerating individuals.
The broad non-submodular version is a Class C candidate in my view: fractional seed allocation does not remove the cascade’s synergy, and the final-spread objective can remain nonconcave. That is a research conjecture, not a hardness result from this paper. I would look for tractable Class A regions under additional concavity or contraction conditions. If \(\tau\) grows enough to preserve arbitrary graph structure, Class B hardness may also arise. Useful follow-up questions are whether fixed \(\tau\) already permits continuum-specific hardness, and which response conditions make the mass-allocation objective tractable.
The paper’s \(\Theta(\sqrt n)\) comparison with greedy is suggestive evidence that synergy matters, but I would not claim that its ratio carries over: its construction uses a discrete seed budget of \(k=2\), and the comparison scales with individual vertex count. My weakest point is more basic. In a realized graph, a node’s relevant type may include a detailed neighborhood; then grouping genuinely indistinguishable agents can leave \(\tau\) close to the population size. The mirror is strongest for block-exchangeable populations with repeated contact roles. It does not cover arbitrary observed social graphs, and the aggregate contact model may smooth away local network motifs that drive the paper’s examples. That narrows the case, but leaves a recognizable influence-maximization problem whose society, seed decision, and outcome are all expressed in mass.
The strongest negative starts with the proposed anchor. Theorem 1 gives DPIM an \(O(nk^2)\) bound on calls to the influence oracle \(\sigma\). That is a real algorithmic result, but it bounds one heuristic’s oracle use; the paper does not classify the computational complexity of Influence Maximization itself. Theorem 2 compares solution quality with greedy, and the experiments do the same empirically. Neither supplies a complexity result for a continuous mirror to carry forward.
The proponent’s type-level formulation is the strongest repair. It gives a coherent optimization problem, but its recurrence is a mean-field closure: each type’s infection rate depends on the infected *share* of its contacts. The paper’s cascades depend on the infected *set* of each node’s neighbors. With nonlinear responses, those are different information. A contact matrix and type-level infected masses do not generally preserve neighborhood overlap, clustering, or the local synergies the paper studies.
An exact repair would have to retain enough contact structure to reproduce those effects. In the paper’s sparse networks, that can make types nearly as numerous as nodes. A finite-block model avoids that problem by assuming exchangeability within blocks, but then the question concerns seed allocation in a stylized aggregate cascade. It does not transfer DPIM’s dynamic program over a hierarchy of individual network vertices, or its oracle-call bound. It also changes the role of complex contagion: a threshold of two infected neighbors becomes a response to an infected share, whose scale must be chosen separately.
So the best case against is that the paper gives little computational-complexity result to mirror, and preserving its network-level cascade behavior may leave no useful population compression. That case is strong against this paper’s theorem as an anchor. It is weaker against the universal claim. A finite-type, exchangeable network can be a sensible population regime; choosing an \(\alpha\) fraction of each type as seeds and studying nonlinear spread is a well-posed computational question. I cannot honestly rule out that mirror as worthwhile. The negative verdict is strongest if “mirror” means extending the paper’s stated algorithmic result, and much less secure if it includes a new continuous influence-maximization problem the authors would recognize.
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.