When a platform's moderation team sees a false story spreading, it decides which accounts to throttle, label, or answer with a correction. It has a fixed number of reviewer-hours, and different accounts cost different amounts to act on. The algorithmic literature says this problem is hopeless to approximate well: blocking vertices to minimize spread on a general social graph is APX-hard, and multi-cascade containment cannot even be approximated within a polylogarithmic factor. As a result, deployed and published methods are heuristics with no worst-case guarantee. Our observation is that the object a moderator actually acts on is not the whole follower graph. It is the cascade already observed, meaning who reshared from whom, and that object is close to a tree. On trees and forests, the budgeted version of the problem is only weakly NP-hard. It therefore admits a fully polynomial-time approximation scheme (FPTAS): an algorithm that, for any error tolerance $\epsilon$, returns a plan within a factor $(1-\epsilon)$ of the best possible, in time polynomial in both the cascade size and $1/\epsilon$.
We propose to build this scheme for budgeted intervention across many concurrent cascades, each weighted by a fake-news detector's confidence and by a learned prediction of each account's future reach. We will then test the two claims that decide whether it matters. The first is whether optimizing exactly on the observed tree beats strong heuristics run on the full graph, once outcomes are simulated on the full graph. The second is whether the guarantee survives the error in the learned predictions that it takes as input. The FPTAS is the core mechanism. Fake news spreading is the application that supplies tree structure, heterogeneous costs, and the timing pressure that makes fast, certified answers valuable.
Core Claim
Restricting to observed cascade forests with heterogeneous intervention costs gives a problem that is weakly NP-hard, because a single star-shaped cascade already encodes the classic knapsack problem. The same problem admits an FPTAS through a two-level dynamic program. Within each cascade tree, the program computes, for each discretized amount of averted harm, the minimum cost of achieving it. Across cascades, it merges these cost curves under the shared budget. Concretely, let cascade $j$ have detector-estimated probability $q_j$ of being false. Let each currently active account $v$ in its tree $T_j$ have predicted residual future exposures $w_v$. Throttling account $u$ costs $c_u$ and stops the future exposures of $u$ and of every not-yet-realized descendant. We solve
$$\max_{S} \sum_j q_j \sum_{v \in T_j} w_v \,\mathbf{1}[\text{some ancestor-or-self of } v \text{ is in } S] \quad \text{s.t.} \quad \sum_{u \in S} c_u \le B,$$
where $S$ is the set of throttled accounts and $B$ is the reviewer budget. Rounding harm values to multiples of $\epsilon V / N$, with $V$ the largest single-account value and $N$ the total number of nodes, gives a table of size polynomial in $N/\epsilon$. Standard profit-rounding arguments then give the $(1-\epsilon)$ guarantee.
The novelty claim is not that tree knapsack can be solved with rounding; that is textbook. The claim is that this tractable class is the operationally relevant one for misinformation, and that it yields certified plans. Because the scheme computes a near-tight bound on the optimum, it can also certify how far any heuristic, including the ones moderators use today, falls from the best achievable plan.
Relation to Prior Work
Three papers motivate the gap by showing that existing containment methods have no a priori guarantee. On Misinformation Containment in Online Social Networks proves non-monotonicity and polylogarithmic inapproximability for multi-cascade containment. It then uses a sandwich strategy, greedy optimization between submodular upper and lower bounds, which gives only instance-dependent bounds. Misinformation Mitigation under Differential Propagation Rates and Temporal Penalties extends this to a setting where fake news travels about six times faster than truth, and also relies on sandwich bounds. Minimizing the Influence of Misinformation via Vertex Blocking proves APX-hardness of general-graph blocking and replaces Monte Carlo simulation with dominator trees, speeding up greedy search by up to six orders of magnitude, but it provides no approximation guarantee.
These hardness results also constrain our design. We do not claim anything on general graphs. Instead, we move to the observed-cascade forest, where the APX-hardness reduction does not apply. A side note: on a tree, the dominator tree is the tree itself, so the AdvancedGreedy method from the vertex-blocking paper reduces to a subtree-weight greedy. That makes it a natural, strong baseline in our setting.
Two papers supply the method. To Store or Not to Store: a graph theoretical approach for Dataset Versioning shows the template we follow: a problem that is inapproximable on general graphs becomes FPTAS-solvable on bounded-treewidth graphs or arborescences through cost discretization and tree dynamic programming. Subsidy Allocations in the Presence of Income Shocks supplies the cross-agent budget-discretization step, together with a warning we take seriously. An FPTAS is only as good as the parameters it is given, and those parameters are hard to estimate from noisy observational data. In our setting, those parameters are the reach predictions $w_v$ and the detector scores $q_j$.
The detection literature supplies the inputs. Words are the Window to the Soul: Language-based User Representations for Fake News Detection and FACTOID: A New Dataset for Identifying Misinformation Spreaders and Political Bias show that user timelines and interaction graphs carry predictive signal about spreaders. We reuse that signal to predict residual reach. Transparent Tagging for Strategic Social Nudges on User-Generated Misinformation shows that detector errors change how much effort content providers put into authenticity. We do not model those incentives, and we name this as a limitation.
Research Program
The first stage is theory and implementation. We will prove weak NP-hardness by reduction from knapsack on a star and prove the $(1-\epsilon)$ guarantee for the two-level program. We will also extend the model so that each account has a choice of action level, such as label, throttle, or seed a correction, with different costs and partial effects. Each node then carries a small menu of actions instead of a single on/off choice, and the dynamic program grows by only a constant factor.
The second stage handles departures from trees. Some users see a story from several parents, which turns the exposure structure into a directed acyclic graph. We will measure the treewidth of these exposure structures on real cascades; treewidth is a measure of how close a graph is to a tree. If it is small, we will lift the dynamic program to a tree decomposition, in the style of the dataset-versioning paper. If it is large, we will report that negative finding and fall back to keeping the heaviest-parent spanning tree.
The third stage connects the scheme to learned inputs. We will train reach predictors from user language and cascade history, and use detector probabilities for $q_j$. We will then quantify how prediction error degrades the realized objective. The specific bound is that if each $w_v$ is off by at most a multiplicative factor $(1\pm\delta)$, the plan remains $(1-\epsilon)(1-\delta)/(1+\delta)$-optimal for the true weights. We will also test this empirically.
Baselines
The naive reference points are doing nothing and the platform heuristic of throttling the accounts with the most followers or the highest predicted reach until the budget runs out. That heuristic is what a moderation queue sorted by risk implements. For it, the subsidy paper proves an $\Omega(\sqrt{n})$ efficiency loss in a related allocation setting, which suggests the gap may be real.
The strongest existing method is AdvancedGreedy and GreedyReplace from the vertex-blocking paper. We will run them on the full follower graph, not just the cascade tree, so they see strictly more structure than our method does, and we will give them the same per-node costs by using a cost-ratio rule. That paper reports up to six-orders-of-magnitude speedups over Monte Carlo greedy, but the file reports no exact spread-reduction figure: no reported result found on Lacuna for GreedyReplace residual spread. The closest reported containment number is from the misinformation-containment paper: on Higgs-10K with 20 seeds, the sandwich algorithm reduced misinformation-active nodes from about 180 to 100, while baselines barely got below 160. We will reproduce the sandwich algorithm on Higgs-10K as a second strong competitor, using correction seeds instead of blocking.
The exact reference is an integer linear program solved to optimality on instances small enough to finish. This calibrates the true optimality gap of every method.
The ablation that isolates our key ingredient replaces the dynamic program with a cost-ratio greedy that uses exactly the same tree, weights, and detector scores. Any gain over this ablation is attributable to near-optimal combinatorial search rather than to better inputs. A second ablation sets all $q_j=1$, which isolates the value of detector weighting.
All methods receive identical cascades, cost models, reach predictions, and wall-clock limits. Outcomes are scored by independent-cascade simulation on the full graph rather than by our own tree objective.
Beating the strongest baseline means two things on FakeNewsNet and the SNAP graphs. First, lower simulated harm at equal budget than GreedyReplace on the full graph, with a gap larger than the Monte Carlo confidence interval. Second, staying within 1% of the integer program at $\epsilon = 0.01$ while running within platform latency.
Why not just…?
Why not just use a cost-ratio greedy on the cascade tree? This is the most serious threat. On real cascades, which tend to be shallow and broad, greedy may land within a percent or two of optimal. The ablation above measures exactly this. If greedy is near-optimal on real data, the contribution narrows to certification: the FPTAS supplies the bound that proves greedy's quality, and adversarial deep-and-narrow instances show where greedy breaks. The dataset-versioning paper found a local greedy nearly 1,000 times worse than its dynamic program on the 996.ICU repository, which shows such gaps can arise on real structured data. We will report honestly which regime misinformation cascades fall into.
Why not just solve an integer program? Commercial solvers will likely handle single trees with thousands of nodes. The question is whether they hold up with thousands of concurrent cascades re-planned every few minutes. We will compare runtime distributions, especially the worst case, against the FPTAS's guaranteed polynomial bound. If the integer program is fast enough everywhere we test, we will say so. The scheme's remaining advantages would then be its predictable runtime and an accuracy knob that can be tuned for whatever time is available.
Why not just run the dominator-tree heuristics on the full graph, which sees more edges? The tree abstraction discards non-tree exposure paths, and that could cost more than exact optimization gains. This is why all scoring is done by full-graph simulation. The treewidth measurement in the second stage tells us how much structure is being discarded.
Why not just improve the detector? Better detection improves $q_j$. But the misinformation-containment paper shows that how a fixed budget is spread across the network changes outcomes substantially, from about 180 down to 100 active nodes against baselines stuck near 160. Allocation and detection are complementary, and the $q_j=1$ ablation measures how much detection weighting contributes.
Proposed Experiments
The main testbed is the propagation networks in FakeNewsNet, using the PolitiFact and GossipCop subsets. We replay each cascade up to an intervention time $t$, plan using only what has been observed by then, and score the realized and simulated future exposures that the plan averts. Detector scores come from a fine-tuned classifier. For reference, the file reports Social Article Fusion at about 69.1% accuracy on PolitiFact and RumorLLM-augmented DeBERTa at 93.91% accuracy on PolitiFact. Reach predictors use user timelines and descriptions, following the Words-are-the-Window setup. Costs are modeled as review time that grows with audience size, and we vary the cost model to test sensitivity.
For scale and full-graph realism, we use Higgs-10K and Higgs-100K and the SNAP graphs: Facebook, Wiki-Vote, Twitter, and Youtube with 1.1 million nodes. On these, we generate cascades under independent-cascade diffusion, and under the six-times speed differential from the temporal-penalties paper, using Gnutella and DBLP.
Four checks decide the project. The first is the realized-harm gap between our method and GreedyReplace on the full graph. If it is not positive, the tree restriction is too lossy, and we would report that. The second is the optimality gap versus the integer program and versus the cost-ratio greedy, on both real and adversarially constructed trees. The third is the runtime of the scheme versus the integer program as the number of concurrent cascades grows to the thousands. The fourth is degradation under injected reach-prediction noise of controlled size $\delta$, compared against the predicted $(1-\delta)/(1+\delta)$ bound. If the guarantee loses all value at realistic noise levels, that result sharpens the subsidy paper's parameter-sensitivity warning into a quantitative one for this domain.
References
- On Misinformation Containment in Online Social Networks
- Misinformation Mitigation under Differential Propagation Rates and Temporal Penalties
- Minimizing the Influence of Misinformation via Vertex Blocking
- To Store or Not to Store: a graph theoretical approach for Dataset Versioning
- Subsidy Allocations in the Presence of Income Shocks
- Words are the Window to the Soul: Language-based User Representations for Fake News Detection
- FACTOID: A New Dataset for Identifying Misinformation Spreaders and Political Bias
- Transparent Tagging for Strategic Social Nudges on User-Generated Misinformation
- FakeNewsNet: A Data Repository with News Content, Social Context, and Spatiotemporal Information for Studying Fake News on Social Media