| paper | d4-conf-aaai-2012-0153 |
| 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, already for \(d=1\), with dyadic rational inputs and an inverse-polynomial threshold gap. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), rational meeting probabilities \(m_{st}\), transmission intensities \(P_{st}\), a deadline \(d\), seed-mass budget \(\kappa\), and threshold \(\rho\), does there exist \(x_t\in[0,\mu_t]\) with \(\sum_t x_t\le\kappa\) whose limiting expected active fraction by step \(d\) is at least \(\rho\)? For the IC-M version, set \(z_t=x_t/\mu_t\), \(q_t(0)=z_t\), \(q_t(-1)=0\), and \(\Delta q_t(a)=q_t(a)-q_t(a-1)\); for \(r=1,\ldots,d\), require \(q_t(r)=z_t+(1-z_t)\left[1-\exp\left(-\sum_{s\in T}\mu_sP_{st}\sum_{a=0}^{r-1}\Delta q_s(a)(1-(1-m_{st})^{r-a})\right)\right]\), and test whether \(\sum_t\mu_tq_t(d)\ge\rho\).
A typed block-mixing population with mass \(\mu_t\) per type, seed mass \(x_t\), per-pair transmission probability scaled as \(P_{st}/N\) in finite approximants, and type-pair first-meeting probability \(m_{st}\). The objective is to maximize the limiting fraction activated by deadline \(d\), subject to total seed mass at most \(\kappa\).
The mirror covers the IC-M and LT-M time-critical spread-maximization objectives represented over typed population masses. It leaves the MIA-M, MIA-C, and LDAG-M heuristics, experiments, and login-event appendix outside its scope.
My lead is a continuous mirror of Theorem 1. The paper proves that time-critical influence maximization under IC-M is NP-hard: setting every meeting probability to \(1\) and the deadline to \(|V|\) recovers ordinary IC influence maximization, whose hardness the paper cites from Kempe et al. [10]. Theorem 1 is proved in this paper by that reduction.
The mirror is Typed-Mass IC-M Influence Maximization. Its instance has a finite set of types \(T\), rational population masses \(\mu_t>0\) summing to \(1\), a deadline \(d\), and a seed budget \(\kappa\). A type is a network archetype: its members have the same meeting and transmission parameters to every other type. Write \(m_{st}\) for the meeting probability from type \(s\) to type \(t\), and \(P_{st}\) for their aggregate transmission rate. In the finite-population approximants, there are \(N\mu_t\) members of type \(t\), every directed pair of types \(s,t\) has meeting probability \(m_{st}\), and its transmission probability is \(P_{st}/N\). This scaling keeps total influence on each person finite as the population grows.
A solution is a seed-mass allocation \(x_t\in[0,\mu_t]\), with \(\sum_t x_t\le\kappa\), maximizing the expected fraction of the population activated by step \(d\) in the \(N\to\infty\) limit. To specify that objective, let \(z_t=x_t/\mu_t\), and let \(q_t(r)\) be the fraction of type \(t\) active by step \(r\). Set \(q_t(0)=z_t\), \(\Delta q_t(a)=q_t(a)-q_t(a-1)\), and \(q_t(-1)=0\). For \(r=1,\ldots,d\), the mean-field objective is defined by
\[ q_t(r)=z_t+(1-z_t)\left[1-\exp\left(-\sum_{s\in T}\mu_sP_{st} \sum_{a=0}^{r-1}\Delta q_s(a)\bigl(1-(1-m_{st})^{r-a}\bigr)\right)\right]. \]
The quantity to maximize is \(\sum_t\mu_tq_t(d)\). Equivalently, a decision version asks whether some feasible \(x\) achieves at least a specified spread \(\rho\). This is the same deadline-constrained seed-selection objective as the paper’s problem, with a type-level population and fractional seed mass in place of named users and an integer seed set.
The regime is a large platform campaign with millions of users but, say, tens of engagement and contact archetypes. The campaign can seed a fixed small share of the population; within an archetype, users are exchangeable for the model’s purposes. The interaction matrix preserves meaningful differences between communities while allowing each type to contain many agents. The authors should recognize the mirror’s core: choose seeds to maximize expected influence by a deadline, under their first-meeting and transmission rules. The co-modification is the typed mixing model and the per-pair scaling needed for finite per-capita influence.
A second mirror is Typed-Mass LT-M Influence Maximization, anchored by Theorem 3. The paper proves that time-critical influence maximization under LT-M is NP-hard, again by setting all meeting probabilities to \(1\), using deadline \(|V|\), and recovering the ordinary LT problem; that hardness is cited from [10]. For this mirror, use the same population, deadline, budget, and seed-mass allocation, with meeting probabilities \(m_{st}\). Give each type-\(t\) target an incoming weight \(B_{st}/N_s\) from each type-\(s\) source, where \(N_s\) is the size of that source class and \(\sum_s B_{st}\le1\). This keeps the total available influence weight finite.
With \(q_t(0)=z_t\) and the same \(\Delta q_t(a)\), define the LT-M continuum by
\[ q_t(r)=z_t+(1-z_t)\min\left\{1,\; \sum_{s\in T}B_{st}\sum_{a=0}^{r-1}\Delta q_s(a) \bigl(1-(1-m_{st})^{r-a}\bigr)\right\}. \]
The solution is again a feasible allocation \(x\) maximizing \(\sum_t\mu_tq_t(d)\), or an allocation meeting a specified spread threshold. The LT-M question keeps the paper’s threshold-based influence rule and delayed first meetings; it changes the network representation and scales per-person weights with population.
For both mirrors, I expect Class A for approximation. Theorem 2 proves monotonicity and submodularity of the IC-M influence function on finite seed sets, and Theorem 4 proves the same for LT-M. Their continuous seed-mass extensions should be monotone DR-submodular: the mass objective is the population limit of the finite model’s multilinear extension. If its gradients can be evaluated from the recurrences, continuous greedy should give a \((1-1/e-\varepsilon)\)-approximation in time polynomial in the number of types, deadline, input precision, and \(1/\varepsilon\). That would give the prover a concrete question for each anchor: establish the extension and its approximation algorithm, or find where the argument fails. It would not establish exact optimization in polynomial time; that remains a separate question.
The lead is Theorem 1 because the IC-M recurrence makes the delayed, type-level contributions especially explicit. Both anchors cover the paper’s exact time-critical spread-maximization problems, not its MIA-M, MIA-C, or LDAG-M heuristics, its experiments, or the login-event appendix. Further questions include whether the continuum objective is DR-submodular under the precise finite-population limit, whether exact or additive-\(\varepsilon\) optimization is tractable, and how approximation changes when types have internal network structure.
The weakest point is the model change. The paper’s fixed sparse graph can have individual bottlenecks and topology that this exchangeable typed-mixing regime washes out; \(P_{st}/N\) and \(B_{st}/N_s\) also scale per-person influence. So these are credible mirrors for a large, homogeneous platform regime, but they do not carry Theorem 1 or Theorem 3 over to arbitrary fixed networks. The approximation case rests on the paper’s submodularity results plus the continuous extension, which still needs a proof.
The strongest case against the two anchors is that Theorems 1 and 3 get their hardness from choosing positions in a particular graph. In IC-M, a user’s position determines which cascades can reach them and when. In LT-M, it also determines which incoming weights can accumulate against their threshold. For a type to preserve all of that, it must include the user’s relevant neighborhood and edge parameters. In a general input graph, that can make nearly every user a different type, so the continuous population adds little. Merging users who merely share broad labels or average interaction rates loses paths, bottlenecks, and incoming-weight structure.
The proponent’s block-mixing model is the better alternative: it makes users exchangeable within types and scales pairwise influence down as the population grows. But that is a different network regime from the paper’s fixed graph. There is also a budget fork. With a fixed number \(k\) of seeds and per-pair transmission \(P_{st}/N\), finite-deadline spread stays \(O(1)\), so its fraction of the population vanishes. Preserving nonzero fractional spread requires a seed budget proportional to \(N\), which describes mass campaigning rather than the paper’s small-set seed selection. The same issue applies to LT-M with weights \(B_{st}/N_s\): finitely many seeds contribute vanishing weight to each target in the limit.
That is a substantive objection to treating either theorem’s continuous version as a mirror of its fixed-graph hardness result. It does not, however, defeat the best positive-mass version. A typed block model, or a suitably represented graphon model, with a positive seed share gives a coherent deadline-constrained influence-optimization problem. Its setting may be less typical of small-budget viral marketing, but it is plausible, and the authors could recognize it as their problem. Theorems 1 and 3 therefore do have named computational questions to anchor, and the model change alone does not establish that no worthwhile mirror exists. The honest negative case is weak on the universal claim: it argues that the proposed mirrors leave the paper’s graph regime, but cannot rule out a worthwhile continuous-population regime for time-critical influence maximization.
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.