| paper | d4-conf-aaai-2016-0123 |
| 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}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
Given a finite type set \(T\), rational masses \(\mu_t\), initial influenced and mapped masses, rational type-level kernels defining cascade transmission and teaching events, a horizon \(H\), intervention budget \(\beta\), and weight \(\lambda\), choose feasible intervention masses \(x_t^r\) to maximize \(\lambda I_H+(1-\lambda)M_H\), where \(I_H\) and \(M_H\) are the resulting expected influenced and mapped masses. For input accuracy \(\epsilon\), find a schedule within \(\epsilon\) of the optimum.
A large outreach population represented by exchangeable types that record intervention eligibility, transmission profile, and disclosure behavior; mass \(\mu_t\) in each type; type-level intervention masses \(x_t^r\); and a scalar objective combining expected influenced mass and expected mapped mass.
Type-level rates and mapped mass do not retain which people or connections are discovered, so the mirror may lose network structure that matters to later influence decisions.
fatal: False
The mirror covers the SIAM computational question anchored by Proposition 1; it leaves the greedy-algorithm propositions, their theoretical bounds, and the experiments without continuous analogues.
My lead is a Type-Mass SIAM mirror: a large public-health population is divided into a moderate number \(\tau\) of intervention-relevant types, and the decision is how much population mass of each type to reach. A type records everything the model uses about a person: their intervention eligibility, influence-transmission profile, and tendency to disclose information about others. The underlying network is represented by type-level contact and teaching rates. This is a co-modification of the network model needed to make a population limit coherent; the object being continuized is still the population.
A plausible regime is a large, recurring outreach programme among homeless youth. There may be many people but relatively few profiles relevant to an intervention: for example, combinations of age, housing situation, service venue, and trust in health workers. The model treats people within each profile as exchangeable, while retaining uncertainty about whom they can influence and whom they will tell an interviewer about. The paper itself motivates SIAM with interventions in homeless populations and incomplete network knowledge, so the setting is close to the authors’ problem. It is also a regime in which agencies could reasonably plan in terms of percentages of a cohort, rather than individual-by-individual counts.
Here is a concrete problem for a prover. Call it Type-Mass SIAM-\(\epsilon\). An instance gives a finite type set \(T\), rational masses \(\mu_t\) summing to one, an initial infected mass and mapped mass for each type, rational type-level influence and teaching kernels, a horizon \(H\), a per-capita intervention budget \(\beta\), a scalarization weight \(\lambda\), and an accuracy \(\epsilon\). At round \(r\), the decision is an intervention mass \(x_t^r\) of each type, with \(\sum_{r,t}x_t^r\leq\beta\) and no person selected twice. The influence kernel specifies a finite-type independent-cascade process; the teaching kernel specifies how interventions reveal previously unmapped people. For example, with Poisson teaching rates \(D_{tu}\), the expected mapped mass of type \(u\) after the schedule is
\[
M_u=\mu_u-(\mu_u-m_u^0)\exp\!\left(-\sum_{r,t}D_{tu}x_t^r\right).
\]
Let \(I_H\) be the expected total influenced mass after the \(H\) rounds and their cascades, and \(M_H=\sum_u M_u\). The task is to find a feasible schedule whose \(\lambda I_H+(1-\lambda)M_H\) is within \(\epsilon\) of optimum. The output is the schedule of type-level intervention masses. This preserves the paper’s trade-off between influence and mapping, while making the action and objective population-level.
The anchor is Proposition 1, proved in this paper. It states: “SIAM is NP-Complete.” The proof reduces an instance of influence maximization on graph \(G\) to SIAM by giving SIAM the full graph initially, \(G_0=G\), and making every node carry no information; solving SIAM then solves the influence-maximization instance. The proposition’s proof is in the paper; the underlying influence-maximization hardness is the cited result of Kempe, Kleinberg, and Tardos (2003). One qualification matters: as written, the proposition calls an optimization problem NP-complete without spelling out its decision language. Its reduction clearly gives the computational content of NP-hardness, but the NP-completeness label needs a formal decision version.
I expect the general Type-Mass SIAM-\(\epsilon\) problem to be a Class C candidate, hard for reasons of its own rather than by an established transfer of Proposition 1’s hardness. A continuous allocation across types, cascades, and information gained across rounds can create a difficult coupled optimization problem, even when the population mass is continuous. But Proposition 1 does not prove that claim: its reduction uses a fully known graph and eliminates mapping, and it does not show hardness for a moderate-support type-mass instance. Determining whether fixed \(\tau\), fixed \(H\), or a restricted class of kernels makes the mirror tractable is part of the question. In particular, a continuous version with the teaching kernel disabled is a natural place to test whether fractional seeding dissolves the discrete influence-maximization hardness.
The scope here is deliberately just Proposition 1’s SIAM complexity claim. The paper’s observation that influence-greedy can perform arbitrarily badly, and its propositions about when balanced greedy performs well, motivate the mirror’s algorithmic questions, but I would not present them as additional complexity anchors. The main follow-ups are whether the type-mass problem admits an additive-\(\epsilon\) algorithm for moderate \(\tau\), whether adaptivity to newly mapped mass changes the answer, and which restrictions on the kernels separate tractable cases from hardness.
The weakest point is that the paper’s object is a graph of individually identified people, and its experiments use networks of 33 to 188 nodes; it does not study a large population with repeated types. Replacing those identities and their particular ties with exchangeable type-level rates may erase some of the value of mapping: discovering that a specific person exists is not the same as learning a type mass. That is a real modeling cost. The positive case survives because a large health-outreach programme can plausibly care about population coverage and type-level spread, and because the paper’s central decision—how to divide limited interventions between spreading influence and learning about the network—remains recognizable in that regime.
The strongest objection is that Proposition 1’s hardness comes entirely from ordinary influence maximization. Its reduction sets \(G_0=G\) and removes teaching, so it says nothing about the computational difficulty of learning a network while influencing it. The proposition also labels an optimization problem “NP-complete” without defining a decision language; the reduction establishes NP-hardness. The proposed Type-Mass SIAM-\(\epsilon\) adds a scalar objective, a horizon, per-capita actions, and teaching-rate kernels. That may be a sensible new problem, but it is not the result Proposition 1 proves.
The deeper mismatch is what “mapping” means. In the paper, selecting a person can reveal particular nodes and edges; those revelations change which cascades are possible and which interventions look best next. The proposed formula \(M_u=\mu_u-(\mu_u-m_u^0)\exp(-\sum_{r,t}D_{tu}x_t^r)\) records expected mass discovered. Type-level rates do not say which people or connections were discovered, or whether two influence paths reach the same person. Two networks can have the same type-level contact rates but different overlap and reachability. Preserving those distinctions requires substantially more than the finite type masses and kernels in the proposed instance.
A more faithful mirror could use types that include each agent’s network position, or a graphon or other detailed model of neighborhoods and disclosure. But arbitrary graphs require distinctions approaching one type per vertex, and even a fine block model replaces the original sparse adjacency structure with interactions among blocks. A rich graphon may preserve the needed correlations, but then the input and its complexity parameters are no longer the paper’s finite-support society; the question has shifted toward optimizing interventions under a specified population-network model. In either case, the bridge from Proposition 1 to the proposed continuous problem is missing.
That leaves a real weakness in the negative case: a large outreach programme with repeated intervention profiles could plausibly support a finite-type epidemic model, and optimizing influence alongside aggregate learning could be worthwhile. The paper’s public-health motivation makes that extension recognizable. I would argue that it is an adjacent SIAM model rather than a continuous mirror of the paper’s computational result, but I cannot honestly rule out its value in every scenario. The case against is strongest on fidelity to the paper’s identity-level mapping task, and weakest against a deliberately aggregate reformulation.
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.