When an epidemic spreads over a contact network and a health authority can treat only a few people per unit time, it has to decide whom to treat as infections appear, without knowing where the disease will jump next. Many rules exist for this choice: treat the best-connected people, treat whoever sits on the frontier of the outbreak, or train a reinforcement-learning agent. For none of them can we say, on a given real network, how much worse the rule is than the best possible causal policy. A causal policy is one that sees only the past. This proposal builds a computable certificate that answers that question. It is a lower bound on the outbreak burden that no causal treatment policy can beat on a specific graph, starting from a specific seed, under a specific budget. Comparing any heuristic's measured burden to this certificate gives an upper bound on its competitive ratio, meaning how many times worse it is than optimal.
The certificate rests on one structural fact. At any moment, new infections arrive at a rate set by the number of contacts between infected and healthy people, which we call the outbreak's boundary. No policy can make the boundary smaller than the smallest boundary any group of that size could have in this graph. That minimum, as a function of group size, is a property of the topology alone. It is computable exactly on small graphs and can be lower-bounded spectrally on large ones. The bound therefore transfers across network families (hub-dominated scale-free graphs, clustered small-world graphs, expanders, real mobility networks) in a way that degree-based reasoning does not.
Core Claim
We study the Susceptible-Infected-Susceptible (SIS) model, in which infected nodes infect each neighbor at rate $\beta$ and recover only when treated, under a total treatment rate $r$. Let $S_t$ be the infected set and $X_t = |S_t|$ its size. Define the edge-isoperimetric profile $m_G(k) = \min_{|S|=k} \mathrm{cut}(S)$, the fewest edges that any $k$-node set of graph $G$ has to the rest of the graph. For every non-anticipating policy, $X_t$ stochastically dominates a one-dimensional birth-death chain:
$$ k \to k+1 \text{ at rate } \beta\, m_G(k), \qquad k \to k-1 \text{ at rate } \min(r, k), $$
started at the seed size $k_0$. The cost we track is the expected cumulative infection $J = \mathbb{E}\int_0^{T} X_t\,dt$ over a horizon $T$, together with the expected extinction time. The certificate $L_G(k_0, r)$ is the chain's value of $J$, and it has a closed form via standard birth-death hitting-time sums. For any policy $\pi$ with measured cost $J_\pi$, we report the certified ratio $\hat\rho_\pi = J_\pi / L_G(k_0,r)$. This quantity upper-bounds $\pi$'s competitive ratio against the online optimum. The online optimum is the best causal policy with unlimited computation, not a clairvoyant "prophet" that foresees every transmission.
The substantive hypothesis concerns the other direction. For frontier-following policies, the realized up-rate is $\beta\,\mathrm{cut}(S_t)$, so their cost is controlled by the boundary excess
$$ \eta_\pi(G) = \sup_t \frac{\mathrm{cut}(S_t)}{m_G(|S_t|)}, $$
which measures how much more boundary the policy's actual outbreak has than the most compact outbreak of the same size. We conjecture that the true competitive ratio of a good frontier policy is governed by $\eta$, and hence by graph geometry, rather than by degree heterogeneity. If this holds, a single graph quantity predicts when simple rules are near-optimal and when they are not, across topology families.
Relation to Prior Work
The construction extends A lower bound on the performance of dynamic curing policies for epidemics on graphs, which uses the same stochastic-dominance reduction to a birth-death walk to prove $\Omega(2^n)$ extinction time for any policy. That paper supplies our method. Its bound holds only when every node starts infected, cutwidth is very high ($W \ge \frac{9C}{19}n\Delta$), and the budget is sublinear, and it compares no specific policy to an optimum. We replace the single cutwidth number with the full profile $m_G(k)$, allow localized seeds, cover intermediate regimes, and turn the bound into a per-instance certificate rather than an asymptotic impossibility result.
The upper-bound side builds on Dynamic Curing and Network Design in SIS Epidemic Processes. That paper approximates the optimal pre-planned curing sequence to within $O(\log^2 k)$ of the optimal impedance, the widest boundary such a sequence must pass through. Its guarantee is offline and combinatorial. We ask how a causal policy using that sequence performs against a causal optimum when spread is stochastic, which the paper leaves open.
Two convex resource-allocation lines, Distributed Resource Allocation for Epidemic control and Optimal Resource Allocation for Competitive Spreading Processes on Bilayer Networks, use geometric programs on linearized or mean-field dynamics. Both are static and equilibrium-based, so they constrain rather than compete with our question.
On the competitive-analysis side, Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities and Prophet Secretary Against the Online Optimal motivate benchmarking against the online optimum rather than a prophet. The first also warns that approximating that optimum is PSPACE-hard in general. Our response to that warning is to use an exact optimum only on small graphs and a relaxation-free structural certificate elsewhere.
Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning supplies the instance-discovery method. There, an adversary agent generating bipartite graphs revealed the structural properties of hard instances, which then enabled a proof. We apply the same game to contact graphs, but our quantity of interest is policy-versus-online-optimum, not matching.
The topology-generalization literature motivates the cross-family test. Approximating Optimization Problems using EAs on Scale-Free Networks shows guarantees that hold on power-law graphs vanish on clustered small-world graphs. Unimodal Thompson Sampling for Graph-Structured Arms shows local sampling degrading under extreme degree variance. Both suggest that the right invariant is not degree-based.
Research Program
The first component is an exact solver for the online optimum on small graphs. For discrete-time SIS with $n \le 14$ nodes and budgets of one to three treatments per step, the state space has $2^n$ infected sets and the action space is $\binom{n}{r}$. Value iteration gives the true causal optimum. This exact optimum is the ground truth against which we test both the certificate's tightness ($L_G / J_{\mathrm{opt}}$) and policies' true competitive ratios.
The second component computes certificates at scale. On small graphs, $m_G(k)$ is exact by enumeration. On large graphs we use the Fiedler bound $\mathrm{cut}(S) \ge \lambda_2 k(n-k)/n$, where $\lambda_2$ is the graph Laplacian's second eigenvalue. The bound remains valid when $m_G$ is replaced by anything below it. Hub-dominated graphs often have small $\lambda_2$, so we expect this bound to be loose there. That is itself a topology-generalization finding, and we will try semidefinite lower bounds on small-set expansion to tighten it.
The third component is adversarial topology search. A graph-editing adversary, trained with reinforcement learning as in the stochastic-matching work, maximizes $J_\pi/J_{\mathrm{opt}}$ for a fixed policy $\pi$ on small graphs. A plain evolutionary edge-flip search runs as a control. We then inspect the discovered graphs for shared structure, for example long thin bridges or strong long ties of the kind Strong long ties facilitate epidemic containment on mobility networks found to seed remote clusters. We also test whether boundary excess $\eta$ explains their hardness.
The fourth component is analysis. We aim to prove a competitive-ratio upper bound for a frontier-greedy policy as a function of $\eta$ and the up/down rate ratio. We also aim to show, via the discovered instances, that degree-ranked policies have no bound of this kind.
Baselines
The naive reference point is uniform random treatment of infected nodes. It answers whether topology matters at all for a given graph and budget.
The static degree-centrality baseline treats the highest-degree currently infected nodes. Practitioners would reach for it first, and Degree Centrality and the Probability of an Infectious Disease Outbreak in Towns within a Region reports that centrality's correlation with outbreak probability falls from 0.38 for peripheral seeds to 0.13 for hub seeds. That result predicts this baseline will be seed-sensitive, and we test the prediction.
The strongest structured competitor is a causal version of the impedance-approximating crusade from Dynamic Curing and Network Design in SIS Epidemic Processes, replanned on the current infected set. We found no reported result on Lacuna for its cumulative infection or extinction time on any benchmark in our file; the only figure is the $O(\log^2 k)$ guarantee.
The strongest learned competitor is a graph-neural-network policy (a network that passes messages between neighboring nodes) trained with proximal policy optimization (PPO) on the same simulator. It follows the setup that reached $-45.2$ million dollars versus $-166.6$ million for a lax baseline in the EpiPolicy C15-B environment in Planning Multiple Epidemic Interventions with Reinforcement Learning. That number comes from a compartmental, non-graph environment, so it is not directly comparable to ours.
All policies share the same simulator, seeds, budgets $r$, horizon, and 1,000 rollouts per instance. Learned policies receive a fixed tuning budget of equal wall-clock across graph families, and hyperparameters are tuned on families different from the test families.
The key ablation replaces $m_G(k)$ in the certificate with a degree-based surrogate, namely the sum of the $k$ smallest degrees minus internal edges. This tests whether the isoperimetric profile, rather than any degree statistic, is what makes the certificate tight across families. The certificate "beats" the baselines in the sense that matters here if two things hold. On small graphs, $L_G/J_{\mathrm{opt}}$ must stay above about 0.5 across families. On large graphs, it must certify at least one policy within a factor of 2, wherever the degree-based surrogate cannot. A policy result counts as decisive if boundary excess $\eta$ predicts true competitive ratio, measured by rank correlation, better than degree variance or clustering coefficient across families.
Why not just…?
Why not just rank nodes by degree or PageRank and treat the top ones? This is cheap and often decent on average. The Leitrim commuting results show centrality's predictive power collapses when the seed is a hub, and the long-tie isolation work reports a 17.1% further reduction in cumulative infections over standard tie heuristics on Shanghai mobility data. Our small-graph experiments compute the true competitive ratio of degree ranking against the exact optimum. The adversarial search will report how large that ratio can be made. If it stays near 1 everywhere, this proposal's policy contribution shrinks to the certificate alone, and we will say so.
Why not just train a reinforcement-learning or graph-neural-network policy and skip the theory? This is a real threat on average-case cost: a well-tuned learned policy may match or beat frontier-greedy. We include it as the strongest baseline. What it cannot do by itself is tell an authority how far from optimal it is on their network. Our certificate supplies exactly that, and it applies to the learned policy too. The adversarial search then tests whether the learned policy has hard topologies of the kind the stochastic-matching work exposed. If the learned policy is both best on average and robust under adversarial graphs, the result becomes "certified learned policies," which is still a useful outcome.
Why not just compare against a clairvoyant prophet, or reuse the all-infected cutwidth bound? A prophet that knows every future transmission can treat each node just before it infects anyone, so ratios against it are inflated by information no causal controller has. The matching literature cited above makes this argument for its own setting. The existing cutwidth bound is valid but applies only to the all-infected start and the extreme-cutwidth regime. Our small-graph experiments report both prophet ratios and online-optimum ratios side by side to show the size of this gap directly.
Why not just solve a geometric program for allocation, as in the convex formulations? Those formulations target the linearized threshold condition under static parameters and allocate rates once. Our question is sequential treatment of a stochastic outbreak from a specific seed. We will still include the geometric-program allocation, applied as fixed per-node treatment priorities, as a static baseline on the 8- and 20-node directed graphs used in the distributed-allocation paper.
Proposed Experiments
Small-graph experiments use all connected graphs up to eight nodes, plus 2,000 sampled graphs with up to 14 nodes from five families: Barabási–Albert scale-free, Watts–Strogatz small-world, random regular expanders, trees, and two-community graphs joined by sparse long ties. Adversarially discovered graphs are added to this pool. For each graph we measure certificate tightness, true competitive ratios of all baselines across seeds (hub, periphery, random) and budgets, and whether $\eta$ predicts those ratios.
Large-graph experiments use Barabási–Albert and Watts–Strogatz graphs with up to $10^4$ nodes, plus the human contact and email networks used in the dynamic-curing paper. Where we can rebuild them, we also use the NYC SafeGraph neighborhood mobility graph from Controlling Epidemic Spread: Reducing Economic Losses with Targeted Closures and the Leitrim commuting network; the file gives no resource identifiers, so access must be confirmed. On these graphs we report certified ratios $\hat\rho_\pi$, the fraction of instances on which some policy is certified within a factor of 2, and how certificate tightness varies with $\lambda_2$ and the profile.
Three decisive checks determine whether the idea holds. First, the certificate must be within a small constant of the exact online optimum on small graphs across all five families. If it is only tight on expanders, the topology-generalization claim fails. Second, boundary excess must explain competitive ratios across families better than degree statistics do. Third, the adversarially discovered hard graphs must share a describable structure that we can turn into a proved lower bound on some policy's ratio.
References
- A lower bound on the performance of dynamic curing policies for epidemics on graphs
- Dynamic Curing and Network Design in SIS Epidemic Processes
- Distributed Resource Allocation for Epidemic control
- Optimal Resource Allocation for Competitive Spreading Processes on Bilayer Networks
- Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
- Prophet Secretary Against the Online Optimal
- Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning
- Approximating optimization problems using EAs on scale-free networks
- Unimodal Thompson Sampling for Graph-Structured Arms
- Strong long ties facilitate epidemic containment on mobility networks
- Degree Centrality and the Probability of an Infectious Disease Outbreak in Towns within a Region
- Planning Multiple Epidemic Interventions with Reinforcement Learning
- Controlling Epidemic Spread: Reducing Economic Losses with Targeted Closures