| paper | d4-conf-atal-2022-0041 |
| 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}\); the rational-threshold decision version is \(\mathrm{NP}\text{-complete}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given a finite simple graph \(H=(V,E)\), positive rational masses \(a_v\) for accepting-community types and \(b_e\) for rejecting-boundary types, with \(\sum_{v\in V}a_v+\sum_{e\in E}b_e=1\), and a budget \(k\le |V|\), choose exactly \(k\) communities to seed, one seed per chosen community, to maximize \(\Pi(S)=\sum_{v\in S}a_v-\sum_{e\in E:\,e\cap S\ne\varnothing}b_e\).
The society is a distribution over accepting-community types \(v\in V\) and rejecting-boundary types \(e\in E\), with masses \(a_v,b_e\). Binary decisions \(x_v\in\{0,1\}\) select seeded communities, subject to \(\sum_v x_v=k\); maximize \(\sum_v a_vx_v-\sum_{e:\,\exists v\in e,\ x_v=1}b_e\).
With fixed support, a single seed has vanishing per-capita size as the population grows yet activates an entire community; replacing discrete seeds with mass seeding makes the cascade discontinuous.
fatal: False
The mirror covers Theorem 3.3, the NP-hardness result for unweighted cluster graphs. It does not claim to continuize the approximation, dynamic programming, ILP, heuristic, or experimental results.
The strongest mirror is the paper’s cluster-graph hardness result, Theorem 3.3, proved in this paper. It says that, even when every cluster-graph node and edge has weight \(1\), it is NP-hard to find a set \(S\) of exactly \(k\) nodes maximizing \(\pi(S)\). The authors prove this by reduction from finding a \(k\)-clique in a regular graph.
A natural mass version keeps the paper’s cascade and seed action intact while measuring reached people by fractions. Call it Mass Budgeted Overexposure on Cluster Types. An instance consists of a finite simple graph \(H=(V,E)\), positive rational masses \(a_v\) for accepting-community types and \(b_e\) for rejecting-boundary types, with \(\sum_{v\in V}a_v+\sum_{e\in E}b_e=1\), and a budget \(k\). Each \(v\) represents an accepting component: seeding one member reaches its accepting mass \(a_v\). Each \(e=\{u,v\}\) represents rejecting mass \(b_e\), reached if either endpoint community is seeded. Choose exactly \(k\) accepting types and return a set \(S\) maximizing
\[
\Pi_\mu(S)=\sum_{v\in S}a_v-\sum_{e:\,e\cap S\ne\varnothing}b_e.
\]
Equivalently, a decision version asks whether some such \(S\) has \(\Pi_\mu(S)\ge q\), for a given rational \(q\). Its input size is governed by the type support \(\tau=|V|+|E|\), the graph, and the mass bit length \(L\), rather than by the number of people represented.
The intended regime is a large marketing population organized into relatively few cascade roles. Members of an accepting type have the same acceptance status, lie in the same mutually reachable accepting component, and have the same effect when seeded. Members of a rejecting type have the same exposure condition. For example, a community might contain many accepting customers, while a boundary type contains critical customers exposed by either of two communities. The population could have \(N=r(|V|+|E|)\) people for large \(r\), while the support remains \(\tau=|V|+|E|\). These are complete types for the reachability and payoff calculation the paper studies.
The correspondence is exact on Theorem 3.3’s unweighted instances. If \(Z=|V|+|E|\), give each type mass \(1/Z\). Then \(\Pi_\mu(S)=\pi(S)/Z\), so the maximizing seed sets are unchanged. Replicating each type’s members equally raises population size without changing those masses or the optimization problem. The authors should recognize this as their cluster-graph problem with counts expressed as population shares. The mirror covers the paper’s unweighted cluster-graph hardness result; it does not claim to continuize every algorithm or the general instance model.
I expect hardness to transfer. The reduction’s combinatorics live in the graph of community types, and normalizing the masses preserves the objective ordering. The continuous description does not remove the choice among the \(k\) types. This also suggests questions about exact hardness for arbitrary rational masses, approximation guarantees, and how restrictions such as bounded degree or treewidth change the complexity.
The weak point is that the campaign action remains discrete: one seed placement selects a type, even though the population payoff is measured continuously. That fits the paper’s budget of seed placements and a large-market setting where one placement can activate a whole accepting community. If a continuous mirror must also allow fractional seeding mass within each type, this formulation needs another modeling choice: in the paper’s cascade, any positive seed can activate a whole component, so fractional seeding risks making the budget ineffective. The mass formulation is therefore a credible population continuization for the paper’s cluster-restricted question, with its scope and action granularity stated explicitly.
Theorem 3.3 is the strongest anchor, and it is a genuine computational result. The negative case is that the proposed mass formulation changes the units of the objective without giving the budgeted cascade a well-behaved continuum limit.
Replicating every accepting and rejecting role \(r\) times leaves the support and the normalized masses unchanged. Yet one seed still activates an entire accepting cluster: its per-capita cost tends to zero as the population grows, while its payoff remains a positive fraction of society. In a measure-valued seeding model, zero seed mass activates nothing, but any positive seed mass activates the whole cluster. The objective jumps at zero. If instead the budget scales with population while the support stays fixed, eventually there are enough seeds to activate every cluster. Either way, the natural limit loses the paper’s nontrivial budget tradeoff.
The rescue is to keep one binary seeding choice per cluster. But then the optimization is still over a finite cluster graph, with objective coefficients expressed as masses. For rational masses, clearing denominators turns them into integer node and edge weights; the paper already formulates weighted cluster-graph optimization with an ILP. The correspondence \(\Pi_\mu(S)=\pi(S)/Z\) on the unweighted instances is especially direct: it preserves the objective ordering by normalization. This makes the proposed mirror look more like a change of units for the existing problem than a new continuous computational question.
A stronger alternative would charge for seeded population mass, but the cascade’s “one seed activates the cluster” rule makes any positive mass sufficient. Replacing that rule with fractional adoption would define a different cascade model, rather than a continuization of Theorem 3.3. Letting the number of distinct cluster roles grow with the population avoids fixed-support saturation, but then the graph structure driving the problem grows too; the replicated population has not smoothed the decisions.
This is a real objection to the proposed anchor, but it does not establish the requested universal negative. A large market with finitely many interchangeable communities, where one seed can activate a community, is plausible, and the authors might regard its mass-based payoff as their problem. The honest case against is therefore weak: the exact mirror lacks a natural nontrivial mass-budget limit, but I cannot rule out a worthwhile continuous formulation that retains type-level seeding.
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.