Network-Based Interventions for HIV Prevention via Cascade-Aware Suppression of Transmission

# Network-Based Interventions for HIV Prevention via Cascade-Aware Suppression of Transmission
Source: [https://arxiv.org/html/2605.20218](https://arxiv.org/html/2605.20218)
Akseli Kangaslahti Harvard University akselikangaslahti@g\.harvard\.edu&Davin Choo11footnotemark:1 Harvard University davinchoo@seas\.harvard\.edu&Milind Tambe Harvard University tambe@seas\.harvard\.edu&Alastair van Heerden University of Witwatersrand Wits Health Consortium alastair\.vanheerden@wits\.ac\.za&Cheryl Johnson World Health Organization johnsonc@who\.int

###### Abstract

Treating and preventing Human Immunodeficiency Virus \(HIV\) remains a critical global health challenge\. While antiretroviral therapy provides a path toward viral suppression — effectively eliminating an individual’s transmission risk — systemic resource constraints limit the reach of intervention efforts\. This work addresses the strategic distribution of intensive resources among virally unsuppressed individuals to minimize the expected cascade of new infections within a transmission network\. We formalize this challenge as a novel constrained optimization problem where we have resources to “treat”kkout of a set𝐏\\mathbf\{P\}of virally unsuppressed individuals, and establish its theoretical connections to existing computational literature\. We then propose Cascade\-Aware Suppression of Transmission \(CAST\), a polynomial\-time\(δ,ϵ\)\(\\delta,\\epsilon\)\-approximation algorithm that achieves a2​\|𝐏\|2\\sqrt\{\|\\mathbf\{P\}\|\}approximation ratio by leveraging connections to the Minimum\-kk\-Union \(MkU\) problem and Hoeffding\-style concentration bounds\. Extensive evaluations on real\-world HIV networks demonstrate thatCASToutperforms standard public health and computer science baselines\. Furthermore, we show thatCASTis empirically robust across diverse infectious disease networks, varied edge probability initializations, and settings involving imperfect network data\.

## 1Introduction

With more than 40 million individuals infected worldwide, Human Immunodeficiency Virus \(HIV\) remains a critical global health challenge\. While a cure is currently unavailable, proper medical treatment can suppress the virus to levels that effectively eliminate further transmission risk\. Aligned with UN Sustainable Development Goal 3\.3UN\_SDG3, UNAIDS proposed the 95\-95\-95 targets for HIV that aim for 95% of individuals with HIV to be aware of their status, 95% of those aware of their positive status to receive treatment, and 95% of those that are treated to reach viral suppression by 2030unaids2022\. However, public health agencies operate under chronic resource constraints, so optimizing resource allocations for HIV treatment and prevention is essentialsansom2021optimal\. This is an especially urgent problem as public health agencies that are already constrained are currently facing additional budget cuts for HIV prevention effortsten2025impact\. The World Health Organization \(WHO\) has recommended network\-based strategies to help navigate these resource constraintswho\.

In this work, we address one such resource allocation challenge to support network\-based HIV prevention efforts\. Clinical studies have established that virally suppressed individuals do not transmit the viruscohen2011prevention;rodger2016sexual;bavinton2018viral, a finding that anchors the “Undetectable = Untransmittable” \(U = U\) campaignniaid2019hiv;olson2020uu;CDC\_UU\_2024and underpins the public health strategy known as Treatment as Prevention \(TasP\), which leverages individual treatment as a structural tool to reduce population\-level incidenceDHS\_HIV\. However, viral suppression can be hindered by a variety of factors, including medication non\-adherence and limited healthcare access, which in turn contribute to broader drug resistance challenges\. Though public health agencies can provide some support, such as adherence counseling, viral load monitoring, or high\-efficacy treatments, resources are limited\. Thus, when a public health agency identifies a group of individuals that have untreated HIV and/or are virally unsuppressed, they must choose how to strategically allocate these resources to prioritize a limited number of individuals for intensive interventions, with the goal of minimizing the expected cascade of new infections across the community’s transmission network\. For example, this scenario can arise when trying to expand services to reach underserved populations\. Furthermore, since collecting information to understand the full network can be expensive and time consuming, the intervention strategy should ideally adapt well to imperfect networks that are less costly and faster to collect\. We focus on developing an algorithmic approach that can help address this problem\. We conduct this research in close collaboration with domain experts from a large university in South Africa as well as a global nonprofit health organization, with the ultimate goal of deploying our approach in field settings\.[Fig\.˜1](https://arxiv.org/html/2605.20218#S1.F1)shows HIV prevention field work being conducted by our collaborators\.

![Refer to caption](https://arxiv.org/html/2605.20218v1/pics/pic1.jpg)

![Refer to caption](https://arxiv.org/html/2605.20218v1/pics/pic2.jpg)

![Refer to caption](https://arxiv.org/html/2605.20218v1/pics/pic3.jpg)

![Refer to caption](https://arxiv.org/html/2605.20218v1/pics/pic4.jpg)

Figure 1:Images from our collaborators conducting HIV prevention field work in South Africa\.Contributions\.Our theory and simulations show that our proposedCASTalgorithm has strong potential for real\-world impact in improving the efficiency of HIV prevention resources, even under more realistic problem instances with imperfect networks\. More specifically:

1. 1\.Intervention Model: We introduce and formalize the Minimizing Infection via Node Treatment \(MINT\) problem where we have resources to “treat”kkout of a set𝐏\\mathbf\{P\}of virally unsuppressed individuals, a novel optimization problem that captures the objectives and constraints of the real\-world limited resource allocation problem described above\. We analyze and prove important mathematical properties of this problem, showing that its minimization objective is non\-negative, monotonic, and submodular, and thatMINTreduces to a special case of the more well\-studied Influence Minimization \(IMIN\) problem but remains distinct from Influence Maximization \(IM\)\.
2. 2\.Cascade\-Aware Suppression of Transmission \(CAST\): For any fixed realization of the stochastic transmission network, we prove thatMINTis equivalent to the Minimum\-kk\-Union \(MkU\) problem\. By combiningMkUapproximation algorithms with structured sample\-based set constructions and Hoeffding\-style concentration bounds, we provideCAST, a polynomial\-time\(δ,ϵ\)\(\\delta,\\epsilon\)\-approximation algorithm for the generalMINTproblem with a ratio of2​\|𝐏\|2\\sqrt\{\|\\mathbf\{P\}\|\}for expected new infections\.
3. 3\.Empirical Evaluation: We evaluateCASTon public real\-world HIV network datasets in simulation, and compare its performance to several baseline algorithms from related public health and computer science literature\. We show thatCASTconsistently outperforms these baselines across a variety ofMINTinstances and on disease networks beyond HIV\.
4. 4\.Extension to Imperfect Networks: To address practical deployment challenges regarding network collection and observability, we study the effectiveness of treatment decisions on incomplete networks that are less costly and quicker to record, which we supplement with learned link predictions\. Since edge probabilities can also be difficult and expensive to estimate, we further evaluate howCASTadapts to mismatched edge probability initializations\. Our empirical simulations show thatCASTremains robust to these imperfect network settings\.

## 2Preliminaries and Related Work

### Notation\.

We use boldface letters \(e\.g\.,𝐒\\mathbf\{S\}\) for sets and calligraphic letters \(e\.g\.,𝒢\\mathcal\{G\},ℋ\\mathcal\{H\}\) for graphs and random realizations\.

Concentration bounds\.We will use standard concentration inequalities to relate empirical estimates to expectations\. In particular, we use the following form of Hoeffding’s inequality\.

###### Theorem 1\(Hoeffding’s inequalityhoeffding1963probability\)\.

LetX1,…,XnX\_\{1\},\\ldots,X\_\{n\}be independent random variables such thatai≤Xi≤bia\_\{i\}\\leq X\_\{i\}\\leq b\_\{i\}\. Then, for anyε\>0\\varepsilon\>0,

Pr⁡\(\|∑i=1nXi−𝔼​\[∑i=1nXi\]\|\>ε\)≤2​exp⁡\(−2​ε2∑i=1n\(bi−ai\)2\)\\Pr\\left\(\\left\|\\sum\_\{i=1\}^\{n\}X\_\{i\}\-\\mathbb\{E\}\[\\sum\_\{i=1\}^\{n\}X\_\{i\}\]\\right\|\>\\varepsilon\\right\)\\leq 2\\exp\\left\(\-\\frac\{2\\varepsilon^\{2\}\}\{\\sum\_\{i=1\}^\{n\}\(b\_\{i\}\-a\_\{i\}\)^\{2\}\}\\right\)

Probabilistic spread model\.In one\-shot intervention settings like ours, we are interested in the ultimate lifetime spread outcome rather than granular, step\-by\-step temporal dynamics\. We also need to consider spread probabilistically: for sexually transmitted infections like HIV, there may be network edges that never result in transmissiondosekun2010overview\. To this end, we employ the Independent Cascade \(IC\) modelkempe2003maximizingto characterize the diffusion of infections across the network𝒢\\mathcal\{G\}\. In the IC model, when a nodevvbecomes active, it has a single discrete opportunity to activate each successoruuwith probabilityw\(v,u\)w\_\{\(v,u\)\}\. The type and frequency of such shared behavior between two individuals carry a specific risk, making the IC model’s “probabilistic coin flip” a natural representation in our scenario in which an edge activation can be viewed as a cumulative lifetime chance of infection\. Related models like Susceptible\-Infected \(SI\)nakamura2017efficientcan capture more granular transient states and temporal dynamics, but do not offer a natural measurement of the lifetime spread outcome, which is exactly what we are ultimately interested in studying in this work\. In order to adapt such models to one\-shot problems, we would need to either set an arbitrary horizon after which we no longer care about spread, or consider an infinite horizon, under which SI degenerates to simple reachability from source nodes\. From a mathematical perspective, the IC model has a*live\-edge*interpretation: each edge is independently retained with probabilityw\(v,u\)w\_\{\(v,u\)\}to yield a random graph realizationℋ∼𝒢\\mathcal\{H\}\\sim\\mathcal\{G\}\. Under the live\-edge perspective, the diffusion process is equivalent to reachability inℋ\\mathcal\{H\}, so expectations are calculated over the distribution of random graph realizations\.

Influence maximization\.Influence maximization seeks a seed set that maximizes expected spread under stochastic influence models such as the Independent Cascade \(IC\) model and*Linear Threshold*\(LT\) modelskempe2003maximizing\. In contrast to the IC model, the LT model captures cumulative influence, where a node activates once the total influence from its neighbors exceeds a thresholdgranovetter1978threshold;schelling2006micromotives, which is less appropriate in our setting\. A key feature of both models is that the expected spread is monotone submodular, enabling a\(1−1/e\)\(1\-1/e\)\-approximation via greedy algorithmskempe2003maximizing\. Other influence models and corresponding algorithms have since been proposed and studied beyond IC and LT, including Triggeringkhim2016computing, Competitive Influencebharathi2007competitive, and Time\-Delayed diffusionchen2012time, though IC clearly remains the best choice for our setting\.

###### Definition 2\(Influence Maximization \(IM\) under IC\)\.

Given a directed probabilistic graph𝒢=\(𝐕,𝐄,w\)\\mathcal\{G\}=\(\\mathbf\{V\},\\mathbf\{E\},w\)and a budgetk∈ℕk\\in\\mathbb\{N\}, theIMproblem is to choose a seed set𝐒⊆𝐕\\mathbf\{S\}\\subseteq\\mathbf\{V\}with\|𝐒\|≤k\|\\mathbf\{S\}\|\\leq kto maximize𝔼ℋ∼𝒢​\[fℋIM​\(𝐒\)\]\\mathbb\{E\}\_\{\\mathcal\{H\}\\sim\\mathcal\{G\}\}\[f\_\{\\mathcal\{H\}\}^\{\\mathrm\{\\texttt\{IM\}\}\}\(\\mathbf\{S\}\)\]wherefℋIM​\(𝐒\)=\|\{u∈𝐕:uis reachable from𝐒inℋ\}\|f\_\{\\mathcal\{H\}\}^\{\\mathrm\{\\texttt\{IM\}\}\}\(\\mathbf\{S\}\)=\\left\|\\\{u\\in\\mathbf\{V\}:\\text\{$u$ is reachable from $\\mathbf\{S\}$ in $\\mathcal\{H\}$\}\\\}\\right\|\.

Influence minimization and node blocking\.Our work is most closely related to influence minimization via node blockingwang2024efficient;xie2025influence\. The works in this literature typically fix the seed active set𝐐\\mathbf\{Q\}and focus on blocking a set of inactive nodes from𝐕∖𝐐\\mathbf\{V\}\\setminus\\mathbf\{Q\}to minimize total active nodes after influence diffuses through the network\. Under the live\-edge interpretation,IMINis equivalent to removing nodes from each realizationℋ\\mathcal\{H\}and maximizing the reduction in nodes reachable from𝐐\\mathbf\{Q\}\. A key challenge inIMINis that the objective is*not submodular*, which precludes standard greedy\-based approximations and necessitates heuristic or relaxation\-based approacheswang2024efficient;wang2025time\. We will later show thatMINT’s objective can be reduced to a special case ofIMINthat turns out to be an easier problem to solve: our objective is submodular and thus we may leverage known results in submodular*minimization*\.

###### Definition 3\(Influence Minimization \(IMIN\) under IC\)\.

Let𝒢=\(𝐕,𝐄,w\)\\mathcal\{G\}=\(\\mathbf\{V\},\\mathbf\{E\},w\)be a directed probabilistic graph with an initial set of active nodes𝐐⊆𝐕\\mathbf\{Q\}\\subseteq\\mathbf\{V\}\. Given a budgetk∈ℕk\\in\\mathbb\{N\}, theIMINproblem is to choose𝐒⊆𝐕∖𝐐\\mathbf\{S\}\\subseteq\\mathbf\{V\}\\setminus\\mathbf\{Q\}with\|𝐒\|≤k\|\\mathbf\{S\}\|\\leq kto minimize𝔼ℋ∼𝒢​\[fℋIMIN​\(𝐒\)\]\\mathbb\{E\}\_\{\\mathcal\{H\}\\sim\\mathcal\{G\}\}\\\!\\left\[f\_\{\\mathcal\{H\}\}^\{\\mathrm\{\\texttt\{IMIN\}\}\}\(\\mathbf\{S\}\)\\right\]wherefℋIMIN​\(𝐒\)=\|\{u∈𝐕:uis reachable from𝐐inℋ​\[𝐕∖𝐒\]\}\|f\_\{\\mathcal\{H\}\}^\{\\mathrm\{\\texttt\{IMIN\}\}\}\(\\mathbf\{S\}\)=\\left\|\\left\\\{u\\in\\mathbf\{V\}:\\text\{$u$ is reachable from $\\mathbf\{Q\}$ in $\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{S\}\]$\}\\right\\\}\\right\|\.

Minimum\-kk\-Union \(MkU\) and submodular minimization\.The Minimum\-kk\-Union \(MkU\) problem is a central challenge in combinatorial optimization that is closely related to the Maximum Coverage problem, both of which are known to be NP\-hard\. Both problems deal with submodular objectives, but Maximum Coverage admits a\(1−1/e\)\(1\-1/e\)approximation \(which is also known to be tight\)feige1998threshold, whileMkUonly has polynomial time algorithms achieving𝒪​\(n14−ε\)\\mathcal\{O\}\(n^\{\\frac\{1\}\{4\}\-\\varepsilon\}\)and2​m2\\sqrt\{m\}approximations \(which are roughly tight under certain complexity conjectures\)chlamtavc2017minimizing;chlamtac2018densest\.

We formally defineMkUin[Definition˜4](https://arxiv.org/html/2605.20218#Thmtheorem4)and will utilize the2​m2\\sqrt\{m\}approximation ofchlamtac2018densestas a subroutine in our work\. There are also extensions of this approximation algorithm that efficiently approximate submodular minimization problems in generalchen2024extensions\.

###### Definition 4\(MkU\)\.

Considermmsets𝐒1,…,𝐒m⊆𝐔\\mathbf\{S\}\_\{1\},\\ldots,\\mathbf\{S\}\_\{m\}\\subseteq\\mathbf\{U\}over a universe𝐔\\mathbf\{U\}ofnnelements\. Givenk∈ℕk\\in\\mathbb\{N\}, the goal is to find a collection ofkksubsets with the minimum union size\.

Strategic network interdiction\.Several network\-based interventions for preventing spread of disease have previously been studied\. One particularly relevant area of research is on targeted distribution of pre\-exposure prophylaxis \(PrEP\), which is used to protect individuals who do*not*have HIV but are at risk of infectionroberts2022impact\. One common approach is to use learned models to predict individual risk scores to determine which individuals are at greatest risk of infectionmarcus2019use;haas2021machine, rather than considering potential downstream network impacts\. Beyond HIV PrEP, prior work has studied general vaccine distribution to minimize expected new infections, both in one\-shot settingschen2010better;cheng2020outbreakand in sequential settingsdong2024integrating;ling2024cooperating\. In contrast to these works that focus on vaccination \(i\.e\., “removing negative nodes”, similar to theIMINproblem\), our work focuses on virally suppressing infected individuals \(i\.e\., “removing positive nodes”\) which admits a different mathematical structure\. Prior work in optimizing interventions on people living with HIV has been more related to casefinding through network\-based testing rather than achieving viral suppression\. Several studies have shown that targeting networks of recently infected individuals for contact tracing and testing can lead to better prevention outcomesnikolopoulos2016network;morgan2019network\.

## 3Formalizing Real\-World Interventions

We formalize our real\-world problem setting from[Section˜1](https://arxiv.org/html/2605.20218#S1)in[Definition˜5](https://arxiv.org/html/2605.20218#Thmtheorem5)\. Some proofs throughout this section are deferred to[Appendix˜A](https://arxiv.org/html/2605.20218#A1)\.

###### Definition 5\(Minimizing Infection via Node Treatment \(MINT\)\)\.

Let𝒢=\(𝐕,𝐄,w\)\\mathcal\{G\}=\(\\mathbf\{V\},\\mathbf\{E\},w\)be a directed weighted disease transmission graph\. Vertices represent individuals, partitioned into positive \(infected\) nodes𝐏⊆𝐕\\mathbf\{P\}\\subseteq\\mathbf\{V\}and negative \(uninfected\) nodes𝐍=𝐕∖𝐏\\mathbf\{N\}=\\mathbf\{V\}\\setminus\\mathbf\{P\}\. A directed edge\(v,u\)∈𝐄\(v,u\)\\in\\mathbf\{E\}indicates that infection may propagate fromvvtouu, and becomes*live*independently with probabilityw\(v,u\)w\_\{\(v,u\)\}\. Given a budgetk∈ℕk\\in\\mathbb\{N\}, theMINTproblem is to select a subset𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}with\|𝐒\|≤k\|\\mathbf\{S\}\|\\leq kto minimize the expected number of nodes in𝐍\\mathbf\{N\}reachable via live edges from the remaining untreated sources𝐏∖𝐒\\mathbf\{P\}\\setminus\\mathbf\{S\}\.

The existence of an edge\(v,u\)\(v,u\)implies that the corresponding individuals engage in transmission risk behavior such as sexual acts or needle sharing\. The edge weightw\(v,u\)w\_\{\(v,u\)\}indicates the specific probability thatvvwill transmit disease touuif they are or become infected, which depends on factors like risk behavior frequency, condom use, and viral loadboily2009heterosexual;pearson2007modeling\. As positive nodes cannot infect other nodes that are already positive, we may assume without loss of generality that there are no incoming edges to nodes in𝐏\\mathbf\{P\}in theMINTformulation\. This assumption ensures that any directed path originating from a positive node has only negative internal vertices\.

In the probabilistic transmission model ofMINT, there are2\|𝐄\|2^\{\|\\mathbf\{E\}\|\}possible live\-edge realizations\. For any realizationℋ=\(𝐕,𝐄ℋ\)\\mathcal\{H\}=\(\\mathbf\{V\},\\mathbf\{E\}\_\{\\mathcal\{H\}\}\)with𝐄ℋ⊆𝐄\\mathbf\{E\}\_\{\\mathcal\{H\}\}\\subseteq\\mathbf\{E\}, we have

Pr⁡\(ℋ\)=∏e∈𝐄we𝟙​\[e∈𝐄ℋ\]⋅\(1−we\)𝟙​\[e∉𝐄ℋ\]\\Pr\(\\mathcal\{H\}\)=\\prod\_\{e\\in\\mathbf\{E\}\}w\_\{e\}^\{\\mathbbm\{1\}\[e\\in\\mathbf\{E\}\_\{\\mathcal\{H\}\}\]\}\\cdot\(1\-w\_\{e\}\)^\{\\mathbbm\{1\}\[e\\not\\in\\mathbf\{E\}\_\{\\mathcal\{H\}\}\]\}
Given a subset𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}of positive individuals to treat, we remove these nodes from the graph and measure the remaining exposure\. More formally, for a fixed realizationℋ\\mathcal\{H\}, we define

fℋ​\(𝐒\)=\|\{u∈𝐍:uis reachable from𝐏∖𝐒in the directed graphℋ​\[𝐕∖𝐒\]\}\|f\_\{\\mathcal\{H\}\}\(\\mathbf\{S\}\)=\\left\|\\left\\\{u\\in\\mathbf\{N\}:\\text\{$u$ is reachable from $\\mathbf\{P\}\\setminus\\mathbf\{S\}$ in the directed graph $\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{S\}\]$\}\\right\\\}\\right\|\(1\)That is,fℋ​\(𝐒\)f\_\{\\mathcal\{H\}\}\(\\mathbf\{S\}\)counts the number of negative nodes that remain reachable from untreated positives*after*removing treated nodes\. Taking expectation over realizations, we define

F​\(𝐒\)=𝔼ℋ∼𝒢​\[fℋ​\(𝐒\)\]F\(\\mathbf\{S\}\)=\\mathbb\{E\}\_\{\\mathcal\{H\}\\sim\\mathcal\{G\}\}\\left\[f\_\{\\mathcal\{H\}\}\(\\mathbf\{S\}\)\\right\]\(2\)That is, theMINTobjective is exactly minimizingF​\(𝐒\)F\(\\mathbf\{S\}\)under the constraint of𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}and\|𝐒\|≤k\|\\mathbf\{S\}\|\\leq k\.

With the objective represented in terms ofFF,[Proposition˜6](https://arxiv.org/html/2605.20218#Thmtheorem6)tells us that theMINTproblem reduces to a special case ofIMIN\. In fact,MINTadmits a different mathematical structure that is easier to tackle:[Proposition˜7](https://arxiv.org/html/2605.20218#Thmtheorem7)shows that the objective is submodular, soMINTis a special case of submodular minimization and we may leverage on known results in submodular minimization\.

###### Proposition 6\.

MINTcan be reduced to a special case ofIMIN\([Definition˜3](https://arxiv.org/html/2605.20218#Thmtheorem3)\)\.

###### Proof\.

Let𝒢=\(𝐕,𝐄,w\)\\mathcal\{G\}=\(\\mathbf\{V\},\\mathbf\{E\},w\)be aMINTinstance with𝐏⊆𝐕\\mathbf\{P\}\\subseteq\\mathbf\{V\}\. Initialize an auxiliaryIMINgraph𝒢′=\(𝐕′,𝐄′,w′\)\\mathcal\{G\}^\{\\prime\}=\(\\mathbf\{V\}^\{\\prime\},\\mathbf\{E\}^\{\\prime\},w^\{\\prime\}\)with𝐄′=𝐄\\mathbf\{E\}^\{\\prime\}=\\mathbf\{E\},w′=ww^\{\\prime\}=wand𝐕′=𝐕∪𝐐\\mathbf\{V\}^\{\\prime\}=\\mathbf\{V\}\\cup\\mathbf\{Q\}, where\|𝐐\|=\|𝐏\|\|\\mathbf\{Q\}\|=\|\\mathbf\{P\}\|\. In𝒢′\\mathcal\{G\}^\{\\prime\}, nodes from𝐕\\mathbf\{V\}are inactive and the initial active nodes are𝐐\\mathbf\{Q\}\. We associate eachp∈𝐏p\\in\\mathbf\{P\}with a unique active nodeq∈𝐐q\\in\\mathbf\{Q\}, then add a directed edge\(q,p\)\(q,p\)to𝐄′\\mathbf\{E\}^\{\\prime\}with weightw\(q,p\)′=1w^\{\\prime\}\_\{\(q,p\)\}=1\. In this construction, minimizing theMINTobjectiveF​\(𝐒\)F\(\\mathbf\{S\}\)on𝒢\\mathcal\{G\}is equivalent to minimizing theIMINobjective on𝒢′\\mathcal\{G\}^\{\\prime\}, subject to the constraint of𝐒⊆𝐏⊆\(𝐕′∖𝐐\)\\mathbf\{S\}\\subseteq\\mathbf\{P\}\\subseteq\(\\mathbf\{V\}^\{\\prime\}\\setminus\\mathbf\{Q\}\), rather than the more general case where𝐒⊆\(𝐕′∖𝐐\)\\mathbf\{S\}\\subseteq\(\\mathbf\{V\}^\{\\prime\}\\setminus\\mathbf\{Q\}\)\. ∎

###### Proposition 7\.

F​\(𝐒\)F\(\\mathbf\{S\}\)is non\-negative, monotonically non\-increasing, and submodular\.

As bothMINTandIMinvolve selecting a subset of individuals to optimize stochastic influence on the network via independent cascade, it is tempting to viewMINTas a variant of influence maximization\. However, the two problems are fundamentally different in their combinatorial structure\.IMis a coverage problem: it seeks a set𝐒\\mathbf\{S\}that maximizes the size of a union of reachable sets\. In contrast,MINTis an*interdiction*problem: it seeks a set𝐒\\mathbf\{S\}whose*removal*minimizes the size of the union of reachable sets originating from the*remaining*unsuppressed nodes𝐏∖𝐒\\mathbf\{P\}\\setminus\\mathbf\{S\}\. These objectives are not equivalent under any complement\-based transformation of the seed set, primarily becauseIMfocuses on what is gained through selection, whileMINTfocuses on what remains after suppression\.[Proposition˜8](https://arxiv.org/html/2605.20218#Thmtheorem8)formalizes this distinction via a concrete counterexample\. Nevertheless, we include this complement\-basedIMapproach as a baseline in our experiments\.

###### Proposition 8\.

TheMINTproblem is distinct fromIM\. Specifically, let𝐒MINT∗\\mathbf\{S\}^\{\*\}\_\{\\texttt\{MINT\}\}be an optimal solution forMINTand𝐒IM∗\\mathbf\{S\}^\{\*\}\_\{\\texttt\{IM\}\}be an optimal solution forIMrestricted to the same graph𝒢\\mathcal\{G\}, candidate set𝐏\\mathbf\{P\}, and budgetkk\. There exist graph topologies𝒢\\mathcal\{G\}such that𝐒IM∗\\mathbf\{S\}^\{\*\}\_\{\\texttt\{IM\}\}is strictly suboptimal for theMINTobjective\.

###### Proof\.

Consider the graph in[Fig\.˜2](https://arxiv.org/html/2605.20218#S3.F2), and supposewe=1w\_\{e\}=1for all edges so that there is only one live\-edge realization\. Suppose𝐏=\{a,b,c,d\}\\mathbf\{P\}=\\\{a,b,c,d\\\}\. With a budget ofk=2k=2, we see that𝐒MINT⋆=\{c,d\}\\mathbf\{S\}^\{\\star\}\_\{\\texttt\{MINT\}\}=\\\{c,d\\\}anda∈𝐒IM⋆a\\in\\mathbf\{S\}^\{\\star\}\_\{\\texttt\{IM\}\}, resulting inF​\(𝐒MINT⋆\)=1F\(\\mathbf\{S\}^\{\\star\}\_\{\\texttt\{MINT\}\}\)=1andF​\(𝐒IM⋆\)≥2F\(\\mathbf\{S\}^\{\\star\}\_\{\\texttt\{IM\}\}\)\\geq 2\. ∎

aabbccddFigure 2:Suppose𝐏=\{a,b,c,d\}\\mathbf\{P\}=\\\{a,b,c,d\\\}\. With a budget ofk=2k=2, we should treat𝐒=\{c,d\}\\mathbf\{S\}=\\\{c,d\\\}resulting inF​\(𝐒\)=1F\(\\mathbf\{S\}\)=1\. Meanwhile, an influence maximization approach will pick𝐒′\\mathbf\{S^\{\\prime\}\}with nodea∈𝐒′a\\in\\mathbf\{S^\{\\prime\}\}to ensure that all nodes are influenced\. However, doing so necessarily causesF​\(𝐒′\)≥2F\(\\mathbf\{S\}^\{\\prime\}\)\\geq 2\.
## 4Cascade\-Aware Suppression of Transmission \(CAST\)

We now introduce and analyze our approach toMINT, which we call Cascade\-Aware Suppression of Transmission \(CAST\); see[Algorithm˜1](https://arxiv.org/html/2605.20218#alg1)\. We begin by showing a useful relationship betweenMINTand theMkUproblem that we will exploit in the design ofCAST\.

Algorithm 1Cascade\-Aware Suppression of Transmission \(CAST\)1:Infection network𝒢=\(𝐕=𝐏∪𝐍,𝐄,w\)\\mathcal\{G\}=\(\\mathbf\{V\}=\\mathbf\{P\}\\cup\\mathbf\{N\},\\mathbf\{E\},w\), budgetk∈ℕk\\in\\mathbb\{N\}, error toleranceϵ\\epsilon, probabilityδ\\delta

2:𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}⊳\\triangleright\|𝐒\|≤k\|\\mathbf\{S\}\|\\leq k

3:Definem=⌈\|𝐍\|22​ε2​ln⁡2\|𝐏\|\+1δ⌉m=\\left\\lceil\\frac\{\|\\mathbf\{N\}\|^\{2\}\}\{2\\varepsilon^\{2\}\}\\ln\\frac\{2^\{\|\\mathbf\{P\}\|\+1\}\}\{\\delta\}\\right\\rceil⊳\\trianglerightSee[Lemma˜12](https://arxiv.org/html/2605.20218#Thmtheorem12)

4:Samplemmrealizationsℋ1,…,ℋm∼𝒢\\mathcal\{H\}\_\{1\},\\ldots,\\mathcal\{H\}\_\{m\}\\sim\\mathcal\{G\}⊳\\trianglerightPossibly repeated

5:For eachv∈𝐏v\\in\\mathbf\{P\}, define reachability sets𝐑v=\{\(i,u\)∈\[m\]×𝐍:uis reachable fromvinℋi\}\\mathbf\{R\}\_\{v\}=\\left\\\{\(i,u\)\\in\[m\]\\times\\mathbf\{N\}:\\text\{$u$ is reachable from $v$ in $\\mathcal\{H\}\_\{i\}$\}\\right\\\}

6:𝐒′←\\mathbf\{S\}^\{\\prime\}\\leftarrowRun theMkUalgorithm ofchlamtac2018denseston the sets\{𝐑v\}v∈𝐏\\\{\\mathbf\{R\}\_\{v\}\\\}\_\{v\\in\\mathbf\{P\}\}with parameter\|𝐏\|−k∈ℕ\|\\mathbf\{P\}\|\-k\\in\\mathbb\{N\}

7:return𝐒=𝐏∖𝐒′\\mathbf\{S\}=\\mathbf\{P\}\\setminus\\mathbf\{S\}^\{\\prime\}

###### Proposition 9\.

For any fixed realizationℋ∼𝒢\\mathcal\{H\}\\sim\\mathcal\{G\}, the problem of finding a subset𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}with\|𝐒\|≤k\|\\mathbf\{S\}\|\\leq kthat minimizesfℋ​\(𝐒\)f\_\{\\mathcal\{H\}\}\(\\mathbf\{S\}\)is equivalent to theMkUproblem with parameterk′=\|𝐏\|−kk^\{\\prime\}=\|\\mathbf\{P\}\|\-k\.

###### Proof\.

Recall the problem definitions ofMkUandMINTin[Definition˜4](https://arxiv.org/html/2605.20218#Thmtheorem4)and[Definition˜5](https://arxiv.org/html/2605.20218#Thmtheorem5)respectively\. We demonstrate this equivalence by providing a bidirectional reduction between the two problems\.

\(MINT→\\toMkU\):Given a realizationℋ\\mathcal\{H\}, let theMkUuniverse be𝐔=𝐍\\mathbf\{U\}=\\mathbf\{N\}\. For each positive nodev∈𝐏v\\in\\mathbf\{P\}, define a set𝐑v⊆𝐔\\mathbf\{R\}\_\{v\}\\subseteq\\mathbf\{U\}containing all negative nodes reachable fromvvinℋ\\mathcal\{H\}\. Let𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}be the set of treated nodes with\|𝐒\|≤k\|\\mathbf\{S\}\|\\leq k\. The set of untreated nodes is𝐏′=𝐏∖𝐒\\mathbf\{P\}^\{\\prime\}=\\mathbf\{P\}\\setminus\\mathbf\{S\}, where\|𝐏′\|≥\|𝐏\|−k\|\\mathbf\{P\}^\{\\prime\}\|\\geq\|\\mathbf\{P\}\|\-k\. Because nodes in𝐏\\mathbf\{P\}have no incoming edges, a nodeu∈𝐍u\\in\\mathbf\{N\}is reachable from the set𝐏∖𝐒\\mathbf\{P\}\\setminus\\mathbf\{S\}if and only if it is reachable from at least one nodev∈𝐏∖𝐒v\\in\\mathbf\{P\}\\setminus\\mathbf\{S\}in the original realizationℋ\\mathcal\{H\}\. Thus,fℋ​\(𝐒\)=\|⋃v∈𝐏∖𝐒𝐑v\|f\_\{\\mathcal\{H\}\}\(\\mathbf\{S\}\)=\|\\bigcup\_\{v\\in\\mathbf\{P\}\\setminus\\mathbf\{S\}\}\\mathbf\{R\}\_\{v\}\|\. Minimizingfℋ​\(𝐒\)f\_\{\\mathcal\{H\}\}\(\\mathbf\{S\}\)is therefore equivalent to selectingk′=\|𝐏\|−kk^\{\\prime\}=\|\\mathbf\{P\}\|\-ksets from\{𝐑v\}v∈𝐏\\\{\\mathbf\{R\}\_\{v\}\\\}\_\{v\\in\\mathbf\{P\}\}to minimize the size of their union\.

\(MkU→\\toMINT\):Consider anMkUinstance with sets𝒳=\{X1,…,Xm\}\\mathcal\{X\}=\\\{X\_\{1\},\\ldots,X\_\{m\}\\\}over universe𝐔=\{u1,…,un\}\\mathbf\{U\}=\\\{u\_\{1\},\\ldots,u\_\{n\}\\\}and a budgetk′k^\{\\prime\}\. We construct a directed bipartite graphℋ=\(𝐕,𝐄ℋ\)\\mathcal\{H\}=\(\\mathbf\{V\},\\mathbf\{E\}\_\{\\mathcal\{H\}\}\)where𝐏=\{p1,…,pm\}\\mathbf\{P\}=\\\{p\_\{1\},\\dots,p\_\{m\}\\\}and𝐍=\{n1,…,nn\}\\mathbf\{N\}=\\\{n\_\{1\},\\dots,n\_\{n\}\\\}\. We add a directed edge\(pi,nj\)\(p\_\{i\},n\_\{j\}\)if and only ifuj∈Xiu\_\{j\}\\in X\_\{i\}\. In this construction,pip\_\{i\}has no incoming edges\. Selectingk′k^\{\\prime\}sets to minimize their union in theMkUinstance is identical to selectingk′k^\{\\prime\}untreated nodes inMINT\(where the treatment budget isk=m−k′k=m\-k^\{\\prime\}\) to minimize the number of reachable negative nodes\. ∎

This equivalence implies thatMINTis NP\-hard and inherits the inapproximability results ofMkU\. Crucially, it justifies our use of the2​\|𝐏\|2\\sqrt\{\|\\mathbf\{P\}\|\}approximation algorithm for the set\-union objective in[Algorithm˜1](https://arxiv.org/html/2605.20218#alg1)\. Furthermore, the proof highlights the importance of the “no incoming edges for𝐏\\mathbf\{P\}” property: without it, the reachability of a nodeuucould depend on paths through other treated nodes, breaking the set\-union structure\.

Leveraging the structural equivalence from[Proposition˜9](https://arxiv.org/html/2605.20218#Thmtheorem9), we present our main theoretical result for this section, which is thatCAST\([Algorithm˜1](https://arxiv.org/html/2605.20218#alg1)\) is a polynomial time approximation algorithm\.

###### Theorem 10\.

For any fixedε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\), let𝐒⋆\\mathbf\{S\}^\{\\star\}be the true optimizer forFFand𝐒^\\hat\{\\mathbf\{S\}\}be the set returned byCAST\([Algorithm˜1](https://arxiv.org/html/2605.20218#alg1)\)\. Then, we havePr⁡\[F​\(𝐒^\)≤2​\|𝐏\|⋅F​\(𝐒⋆\)\+ε⋅\(1\+2​\|𝐏\|\)\]≥1−2​δ\\Pr\\left\[F\(\\hat\{\\mathbf\{S\}\}\)\\leq 2\\sqrt\{\|\\mathbf\{P\}\|\}\\cdot F\(\\mathbf\{S\}^\{\\star\}\)\+\\varepsilon\\cdot\(1\+2\\sqrt\{\|\\mathbf\{P\}\|\}\)\\right\]\\geq 1\-2\\delta\. Furthermore,CASTruns in polynomial time with respect to\|𝐕\|\|\\mathbf\{V\}\|,\|𝐄\|\|\\mathbf\{E\}\|,ε−1\\varepsilon^\{\-1\}, andδ−1\\delta^\{\-1\}\.

To establish[Theorem˜10](https://arxiv.org/html/2605.20218#Thmtheorem10), we prove the following two lemmas\.[Lemma˜11](https://arxiv.org/html/2605.20218#Thmtheorem11)examines the structure of each set𝐑v\\mathbf\{R\}\_\{v\}inCAST\([Algorithm˜1](https://arxiv.org/html/2605.20218#alg1)\) and reveals how these set constructions bridge the gap between the single realization case from[Proposition˜9](https://arxiv.org/html/2605.20218#Thmtheorem9)to the general empirical objective over many sampled realizations\. Meanwhile,[Lemma˜12](https://arxiv.org/html/2605.20218#Thmtheorem12)demonstrates the importance of the choice ofmm, relating the empirical sample meanF^m\\hat\{F\}\_\{m\}to the true expectationFFby applying Hoeffding’s inequality \([Theorem˜1](https://arxiv.org/html/2605.20218#Thmtheorem1)\) to the random variablesXi=fℋi​\(𝐒\)X\_\{i\}=f\_\{\\mathcal\{H\}\_\{i\}\}\(\\mathbf\{S\}\)\.

###### Lemma 11\.

For anymmrealizationsℋ1,…,ℋm∼𝒢\\mathcal\{H\}\_\{1\},\\ldots,\\mathcal\{H\}\_\{m\}\\sim\\mathcal\{G\}and𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}, defineF^m​\(𝐒\)=1m​∑i=1mfℋi​\(𝐒\)\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)=\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}f\_\{\\mathcal\{H\}\_\{i\}\}\(\\mathbf\{S\}\)as the empirical version ofF​\(𝐒\)F\(\\mathbf\{S\}\)defined on themmrealizations\. Then, solvingMkUon\{𝐑v\}v∈𝐏\\\{\\mathbf\{R\}\_\{v\}\\\}\_\{v\\in\\mathbf\{P\}\}andk′=\|𝐏\|−k∈ℕk^\{\\prime\}=\|\\mathbf\{P\}\|\-k\\in\\mathbb\{N\}inCAST\([Algorithm˜1](https://arxiv.org/html/2605.20218#alg1)\) produces𝐒′\\mathbf\{S\}^\{\\prime\}such that𝐒=𝐏∖𝐒′\\mathbf\{S\}=\\mathbf\{P\}\\setminus\\mathbf\{S\}^\{\\prime\}optimally minimizesF^m​\(𝐒\)\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\), with\|𝐒\|≤k\|\\mathbf\{S\}\|\\leq k\.

###### Proof\.

By definition,F^m​\(𝐒\)=1m​∑i=1m\|\{u∈𝐍:∃v∈𝐏∖𝐒​s\.t\.​v→u​in​ℋi\}\|\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)=\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}\|\\\{u\\in\\mathbf\{N\}:\\exists v\\in\\mathbf\{P\}\\setminus\\mathbf\{S\}\\text\{ s\.t\. \}v\\to u\\text\{ in \}\\mathcal\{H\}\_\{i\}\\\}\|\. Let the universe be𝐔=\{1,…,m\}×𝐍\\mathbf\{U\}=\\\{1,\\dots,m\\\}\\times\\mathbf\{N\}\. For eachv∈𝐏v\\in\\mathbf\{P\}, let𝐑v\\mathbf\{R\}\_\{v\}be the subset of𝐔\\mathbf\{U\}containing pairs\(i,u\)\(i,u\)such thatuuis reachable fromvvin realizationℋi\\mathcal\{H\}\_\{i\}, as in[Algorithm˜1](https://arxiv.org/html/2605.20218#alg1)\. Then,

\|⋃v∈𝐏∖𝐒𝐑v\|=∑i=1m\|\{u∈𝐍:∃v∈𝐏∖𝐒​s\.t\.​v→u​in​ℋi\}\|=m⋅F^m​\(𝐒\)\\left\|\\bigcup\_\{v\\in\\mathbf\{P\}\\setminus\\mathbf\{S\}\}\\mathbf\{R\}\_\{v\}\\right\|=\\sum\_\{i=1\}^\{m\}\|\\\{u\\in\\mathbf\{N\}:\\exists v\\in\\mathbf\{P\}\\setminus\\mathbf\{S\}\\text\{ s\.t\. \}v\\to u\\text\{ in \}\\mathcal\{H\}\_\{i\}\\\}\|=m\\cdot\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)So, minimizing the union of\|𝐏\|−k\|\\mathbf\{P\}\|\-ksets in the universe𝐔\\mathbf\{U\}is precisely theMkUproblem, and the claim follows as minimizingm⋅F^m​\(𝐒\)m\\cdot\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)is equivalent to minimizingF^m​\(𝐒\)\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)\. ∎

###### Lemma 12\.

Fix anyε\>0\\varepsilon\>0andδ∈\(0,1\)\\delta\\in\(0,1\)\. Withm=⌈\|𝐍\|22​ε2​ln⁡2\|𝐏\|\+1δ⌉m=\\left\\lceil\\frac\{\|\\mathbf\{N\}\|^\{2\}\}\{2\\varepsilon^\{2\}\}\\ln\\frac\{2^\{\|\\mathbf\{P\}\|\+1\}\}\{\\delta\}\\right\\rceil, for any𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}, we have

Pr⁡\[\|F​\(𝐒\)−F^m​\(𝐒\)\|\>ε\]≤δ\\Pr\\left\[\\left\|F\(\\mathbf\{S\}\)\-\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)\\right\|\>\\varepsilon\\right\]\\leq\\delta

## 5Experiments

We provide empirical evaluations ofCASTcompared to baseline methods through retrospective simulation studies on real\-world infectious disease datasets\. Key experimental settings are described in the main text and[Appendix˜B](https://arxiv.org/html/2605.20218#A2)\. Across all runs in our experiments, the longest runtime for any algorithm was∼\\sim30 minutes on an M4 Pro MacBook with 24 GB of memory, well within practical time limits for real use cases\. Our code will be published in a public GitHub repository in the final version of the paper\.

Datasets\.We use publicly available anonymized real\-world network data from ICPSRICPSRfor our experiments\. This dataset contains networks for several sexually transmitted infections including HIV, Syphilis, and Hepatitis\. In addition to network connections and disease status, each node in a network is also associated with a covariate vector\. Additional details are provided in[Appendix˜B](https://arxiv.org/html/2605.20218#A2)\.

Baselines\.We consider the following baselines in our experiments:

1. 1\.No Blocking: Baseline for how many new infections occur without any intervention\.
2. 2\.Random: Randomly selects a blocker set𝐒\\mathbf\{S\}with the maximal size allowed by the budget\.
3. 3\.Highest Degree: This algorithm selects blocker nodes from𝐏\\mathbf\{P\}with the greatest unweighted degrees, i\.e\., individuals with the greatest number of contacts\. This is a popular heuristic that has been previously studied for interventions on infectious disease networksliu2021efficient;brazia2026reconstructing\.
4. 4\.SandIMIN: We adapt the SandIMIN influence minimization algorithmwang2024efficientwith Monte\-Carlo sampling to theMINTproblem\. We use weighted degree as the lightweight heuristic\.
5. 5\.Greedy: This algorithm greedily constructs𝐒\\mathbf\{S\}by adding nodes one by one with greatest marginal reduction in expected spread, which is estimated through Monte\-Carlo realization samples\. We include this baseline to evaluate naive minimization of theMINTobjective\.
6. 6\.IM: This algorithm adapts the greedy influence maximization algorithm to theMINTproblem\. It first assumes that all nodes in𝐏\\mathbf\{P\}are blocked, then adds nodes one by one to𝐒\\mathbf\{S\}with greatest marginal increase in spread\. This baseline demonstrates the misalignment between the objectives inMINTvs\.IM, as discussed in[Proposition˜8](https://arxiv.org/html/2605.20218#Thmtheorem8)\.

Known networks\.For these experiments, we follow the steps below:

1. 1\.We convert a network from the ICPSR dataset into a directed transmission graph\. All edges from the dataset are converted to bidirectional edges, then any edge going into a node in𝐏\\mathbf\{P\}is removed\. This is because no node can transmit HIV to nodes in𝐏\\mathbf\{P\}, since nodes in𝐏\\mathbf\{P\}are already individuals with HIV \(as discussed in[Section˜3](https://arxiv.org/html/2605.20218#S3)\)\.
2. 2\.We generatea=10a=10weighted graphs𝒢1,𝒢2,…,𝒢a\\mathcal\{G\}\_\{1\},\\mathcal\{G\}\_\{2\},\.\.\.,\\mathcal\{G\}\_\{a\}\. In each graph, all edge probabilities are initialized independently by sampling an edge probability distribution𝒫\\mathcal\{P\}\.
3. 3\.For eachi∈\{1,…,a\}i\\in\\\{1,\.\.\.,a\\\}, algorithms are given𝒢i\\mathcal\{G\}\_\{i\}, intervention budgetkk, andb=50b=50Monte\-Carlo realizations for each single run on a single graph, and then they output a blocker set𝐒i\\mathbf\{S\}\_\{i\}\.
4. 4\.For each run on𝒢i\\mathcal\{G\}\_\{i\}, average new infections are measured via IC withc=50c=50Monte\-Carlo realizations from𝒢i\\mathcal\{G\}\_\{i\}\. We then report the mean±\\pmSE of average new infections across theaagraphs\.

[Fig\.˜3](https://arxiv.org/html/2605.20218#S5.F3)shows performance of all algorithms on the HIV dataset under uniform random edge probabilities and varying intervention budgets\. Although our target application is in HIV prevention, we also provide experimental results on the datasets for Syphilis and Hepatitis, for which prevention efforts also face major resource constraints\. For the experiment on the HIV network, we make three main observations\. First, random interventions perform substantially worse than all other baselines, underscoring the importance of targeted, network\-aware strategies\. Second,CASTconsistently matches or outperforms all baselines, with the largest gains at low intervention budget regimes\. For example, when intervening on only 20% of all HIV\-positive individuals,CASTincurs 56\.1% less average new infections than the next best baseline \(Greedy\) and 88\.3% less than No Blocking\. Third,CASTremains robust across budgets and exhibits low standard error across edge probability initializations\.CASTalso maintains the strongest comparative advantage in other disease networks, especially for lower intervention budgets\. For example,CASTincurs 45\.9% and 41\.2% less average new infections than the best baseline at the 20% budget for the Syphilis and Hepatitis networks, respectively\.

![Refer to caption](https://arxiv.org/html/2605.20218v1/results/core-result.png)Figure 3:Average new infections \(±\\pmSE\) for the HIV \(left\), Hepatitis \(middle\), and Syphilis \(right\) networks, under uniform random edge probabilities and varying intervention budgets\.Ablations on the edge transmission probabilities\.To study the robustness of our empirical evaluations, we consider alternative edge probability initializations on the HIV network, at the fixed intervention budget of0\.20\.2; see the first two plots in[Fig\.˜4](https://arxiv.org/html/2605.20218#S5.F4)\. We consider \(i\) uniform edge probabilities, wherew\(v,u\)=pw\_\{\(v,u\)\}=pfor all edges withppvarying from0\.20\.2to0\.80\.8, and \(ii\) Gaussian edge probabilities, wherew\(v,u\)∼𝒩​\(μ,σ2\)w\_\{\(v,u\)\}\\sim\\mathcal\{N\}\(\\mu,\\sigma^\{2\}\)clipped to \[0, 1\] withσ=0\.2\\sigma=0\.2andμ\\muvarying from0\.20\.2to0\.80\.8\. As expected, the average number of new infections increases with edge probabilities, reflecting higher transmission likelihood\. Nevertheless,CASTremains consistently robust and substantially outperforms all baselines, with its advantage becoming more pronounced at higher transmission rates\. For instance, atp=μ=0\.5p=\\mu=0\.5,CASTachieves59\.7%59\.7\\%\(uniform\) and60\.2%60\.2\\%\(Gaussian\) fewer average new infections compared to the next best baseline\. These gains improve to81\.3%81\.3\\%and82\.4%82\.4\\%respectively atp=μ=0\.8p=\\mu=0\.8\.

![Refer to caption](https://arxiv.org/html/2605.20218v1/results/edge-ablations.png)Figure 4:Average new infections \(±\\pmSE\) on the HIV network with intervention budget fixed at 0\.2 and varying edge probability initializations\. We evaluate different uniform edge probabilities \(left\) and Gaussian edge initializations with different means \(middle\), with fixedσ2=0\.22\\sigma^\{2\}=0\.2^\{2\}\. We also study performance across different uniform edge probabilities when only the forest subgraph of the transmission network is known, which we supplement with link prediction \(right\)\.Imperfect networks\.One practical challenge that network\-based strategies face in general is in collecting network data\. Thus far, our experiments assumed full observability of both the network structure and edge probabilities\. In the following, we challenge these assumptions through evaluations focused on more practical problem instances\. We use𝒢′\\mathcal\{G\}^\{\\prime\}to denote the decision graph that algorithms use to make decisions and𝒢\\mathcal\{G\}to denote the true graph that is used to evaluate those decisions\.

First, we consider imperfect network structures\. In order to observe the full network structure, a public health official must expend significant time and resources on contact tracing, which may be prohibitively expensive\. One option that can be more feasible in populations with high ongoing HIV risk is a peer\-to\-peer referral system known as Respondent\-Driven Sampling \(RDS\)\. In these systems, individuals will recursively refer many of their relevant contacts to HIV services, allowing edges to be collected through referrals\. However, individuals are unlikely to or may not be allowed to accept multiple referrals to the same service from different individuals\. As observed in prior workstein2018stochastic;kangaslahti2026policy, the resulting recorded network has a forest structure and the remaining edges are never recorded\. Although some studies have recognized this observability gap and tried to predict hidden parts of the network structurechen2016seeing;crawford2018hidden, they fall short of evaluating how well these predicted networks support downstream decision\-making\. Thus, it remains largely unclear how useful learned completions of forest structures can practically be in downstream applications such as network\-based interventions\.

To address this, we study a predict\-then\-optimize frameworkelmachtoub2022smartfor solvingMINTgiven only the forest subgraph of the transmission network\. Though we lose the performance guarantees ofCASTunder this model, we empirically evaluate how well it adapts compared to other baselines\. Specifically, our framework operates as follows:

1. 1\.We perform a breadth\-first search projection on each component of the HIV transmission network𝒢\\mathcal\{G\}to formℱ\\mathcal\{F\}, the referral graph with forest structure\.ℱ\\mathcal\{F\}represents the subgraph of𝒢\\mathcal\{G\}that we could cheaply collect through peer\-to\-peer referrals\.
2. 2\.Using the complete networks from the other ICPSR disease network datasets, we train a probabilistic link prediction modelℓ​\(v,u\)\\ell\(v,u\)that predicts the probability of the existence of an edge between any node pair\(v,u\)\(v,u\)within a shared connected component\.
3. 3\.We useℓ\\ellto infer edge probabilities between all node pairs withinℱ\\mathcal\{F\}that share the same connected component and do not already have an existing edge inℱ\\mathcal\{F\}\. We then normalize these predicted probabilities to the scale of the existing edge probabilities inℱ\\mathcal\{F\}and add the resulting weighted edges to the edge set ofℱ\\mathcal\{F\}, forming the decision graph𝒢′\\mathcal\{G\}^\{\\prime\}\.
4. 4\.We task blocking algorithms to solveMINTon𝒢′\\mathcal\{G\}^\{\\prime\}and evaluate decisions on the true𝒢\\mathcal\{G\}\.

We use an SVM\-based link prediction modelscikit\-learn; implementation details are provided in[Appendix˜B](https://arxiv.org/html/2605.20218#A2)\. The rightmost plot in[Fig\.˜4](https://arxiv.org/html/2605.20218#S5.F4)reports results under this setting\. We evaluate using uniform edge probabilities for ease of normalization, though other distributions can be incorporated by scaling predicted probabilities with samples from the edge probability distribution\. Compared to the setting with full network knowledge \(first plot in[Fig\.˜4](https://arxiv.org/html/2605.20218#S5.F4)\), all methods — includingCAST— exhibit only modest performance losses on graphs with low uniform edge probabilities\. For example,CASTincurs 4\.08%, 3\.90%, and 15\.4% more average new infections under uniform edge probabilities of 0\.2, 0\.3, and 0\.4 \(respectively\)\. At edge uniform probabilities of 0\.6 and higher,CASThas roughly equal performance compared to the case with full network knowledge\. This suggests that a forest backbone obtained via peer referrals, augmented with link prediction, can serve as a cost\-effective substitute for complete network reconstruction\. Since accurately estimating transmission risk on every edge can be expensive, we also study robustness to imperfect edge probabilities\. More specifically, we consider two forms of mismatch between true and assumed edge probabilities and find thatCASTremains robust in both cases\. Details are deferred to[Appendix˜C](https://arxiv.org/html/2605.20218#A3)\.

## 6Conclusion and Discussion

Inspired by the real\-world challenges faced by our public health collaborators in achieving and maintaining HIV epidemic control under growing resource constraints, we study the problem of optimally allocating limited interventions — such as adherence counseling and high\-efficacy treatment — to minimize transmission cascades\. In collaboration with these domain experts, we formalize this challenge as theMINTproblem, bridging real\-world epidemiological objectives with constrained optimization\. We then proposeCAST\([Algorithm˜1](https://arxiv.org/html/2605.20218#alg1)\), a polynomial\-time\(δ,ϵ\)\(\\delta,\\epsilon\)\-approximation algorithm with a2​\|𝐏\|2\\sqrt\{\|\\mathbf\{P\}\|\}approximation guarantee\. Empirical results on real\-world networks show thatCASTconsistently outperforms established baselines and remains robust to other resource\-constrained diseases, imperfect network information, and varying transmission dynamics\.

While we are primarily motivated by HIV treatment, theMINTframework applies broadly to other diseases and also beyond public health applications\. In social networks,MINTcould model the deplatforming or suspension of a limited set of influencers \(𝐏\\mathbf\{P\}\) to protect the susceptible user base \(𝐍=𝐕∖𝐏\\mathbf\{N\}=\\mathbf\{V\}\\setminus\\mathbf\{P\}\) from the diffusion of harmful atrocity speech, e\.g\.,jhaver2021deplatforming\. In cybersecurity settings,MINTcould model the removal of a subset of infected machines \(𝐏\\mathbf\{P\}\) to minimize the expected infection of the broader network \(𝐍=𝐕∖𝐏\\mathbf\{N\}=\\mathbf\{V\}\\setminus\\mathbf\{P\}\), e\.g\.,karakose2018node\.

Discussion of broader impacts, ethics, fairness, and limitations to be addressed in future work are provided in[Appendix˜D](https://arxiv.org/html/2605.20218#A4)\.

## References

## Appendix ADeferred proofs

See[7](https://arxiv.org/html/2605.20218#Thmtheorem7)

###### Proof\.

For any arbitrary realizationℋ∼𝒢\\mathcal\{H\}\\sim\\mathcal\{G\}and negative nodeu∈𝐍u\\in\\mathbf\{N\}, define indicator functions

gℋ,u​\(𝐒\)=𝟙​\[uis reachable from𝐏∖𝐒inℋ​\[𝐕∖𝐒\]\]g\_\{\\mathcal\{H\},u\}\(\\mathbf\{S\}\)=\\mathbbm\{1\}\\left\[\\text\{$u$ is reachable from $\\mathbf\{P\}\\setminus\\mathbf\{S\}$ in $\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{S\}\]$\}\\right\]\(3\)Then, we can rewriteF​\(𝐒\)F\(\\mathbf\{S\}\)as follows:

F​\(𝐒\)\\displaystyle F\(\\mathbf\{S\}\)=𝔼ℋ∼𝒢​\[fℋ​\(𝐒\)\]\\displaystyle=\\mathbb\{E\}\_\{\\mathcal\{H\}\\sim\\mathcal\{G\}\}\\left\[f\_\{\\mathcal\{H\}\}\(\\mathbf\{S\}\)\\right\]\(By[Eq\.2](https://arxiv.org/html/2605.20218#S3.E2)\)=𝔼ℋ∼𝒢​\[∑u∈𝐍gℋ,u​\(𝐒\)\]\\displaystyle=\\mathbb\{E\}\_\{\\mathcal\{H\}\\sim\\mathcal\{G\}\}\\left\[\\sum\_\{u\\in\\mathbf\{N\}\}g\_\{\\mathcal\{H\},u\}\(\\mathbf\{S\}\)\\right\]\(By[Eq\.1](https://arxiv.org/html/2605.20218#S3.E1)and[Eq\.3](https://arxiv.org/html/2605.20218#A1.E3)\)Since non\-negativity, monotonicity, and submodularity are preserved under non\-negative linear combinations, it suffices to show thatgℋ,ug\_\{\\mathcal\{H\},u\}is non\-negative, monotonically non\-increasing, and submodular for every realizationℋ\\mathcal\{H\}and everyu∈𝐍u\\in\\mathbf\{N\}\.

In the remainder of the proof, let us fix an arbitrary realizationℋ∼𝒢\\mathcal\{H\}\\sim\\mathcal\{G\}, an arbitrary negative nodeu∈𝐍u\\in\\mathbf\{N\}, arbitrary subsets𝐀⊆𝐁⊆𝐏\\mathbf\{A\}\\subseteq\\mathbf\{B\}\\subseteq\\mathbf\{P\}, and an arbitrary positive nodex∈𝐏∖𝐁x\\in\\mathbf\{P\}\\setminus\\mathbf\{B\}\.

### Non\-negativity and monotonically non\-increasing\.

Sincegℋ,u​\(𝐒\)∈\{0,1\}g\_\{\\mathcal\{H\},u\}\(\\mathbf\{S\}\)\\in\\\{0,1\\\}is an indicator function, it is non\-negative\. Furthermore, treating more positive nodes can only decrease this indicator function: sinceℋ​\[𝐕∖𝐁\]\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{B\}\]is a subgraph ofℋ​\[𝐕∖𝐀\]\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{A\}\]and𝐏∖𝐁⊆𝐏∖𝐀\\mathbf\{P\}\\setminus\\mathbf\{B\}\\subseteq\\mathbf\{P\}\\setminus\\mathbf\{A\}, reachability can only decrease, sogℋ,u​\(𝐀\)≥gℋ,u​\(𝐁\)g\_\{\\mathcal\{H\},u\}\(\\mathbf\{A\}\)\\geq g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\)\.

### Submodularity\.

We need to establish

gℋ,u​\(𝐀∪\{x\}\)−gℋ,u​\(𝐀\)≥gℋ,u​\(𝐁∪\{x\}\)−gℋ,u​\(𝐁\)g\_\{\\mathcal\{H\},u\}\(\\mathbf\{A\}\\cup\\\{x\\\}\)\-g\_\{\\mathcal\{H\},u\}\(\\mathbf\{A\}\)\\geq g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\\cup\\\{x\\\}\)\-g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\)Sincegℋ,ug\_\{\\mathcal\{H\},u\}is monotonically non\-increasing, we always have

gℋ,u​\(𝐀\)≥gℋ,u​\(𝐁\)≥gℋ,u​\(𝐁∪\{x\}\)andgℋ,u​\(𝐀\)≥gℋ,u​\(𝐀∪\{x\}\)≥gℋ,u​\(𝐁∪\{x\}\)g\_\{\\mathcal\{H\},u\}\(\\mathbf\{A\}\)\\geq g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\)\\geq g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\\cup\\\{x\\\}\)\\quad\\text\{and\}\\quad g\_\{\\mathcal\{H\},u\}\(\\mathbf\{A\}\)\\geq g\_\{\\mathcal\{H\},u\}\(\\mathbf\{A\}\\cup\\\{x\\\}\)\\geq g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\\cup\\\{x\\\}\)Sincegℋ,ug\_\{\\mathcal\{H\},u\}is\{0,1\}\\\{0,1\\\}\-valued, we see thatgℋ,u​\(𝐁∪\{x\}\)−gℋ,u​\(𝐁\)≤0g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\\cup\\\{x\\\}\)\-g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\)\\leq 0, so the only nontrivial case to verify is thatgℋ,u​\(𝐁\)=1g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\)=1andgℋ,u​\(𝐁∪\{x\}\)=0g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\\cup\\\{x\\\}\)=0whengℋ,u​\(𝐀\)=1g\_\{\\mathcal\{H\},u\}\(\\mathbf\{A\}\)=1andgℋ,u​\(𝐀∪\{x\}\)=0g\_\{\\mathcal\{H\},u\}\(\\mathbf\{A\}\\cup\\\{x\\\}\)=0\.

In this case, inℋ​\[𝐕∖𝐀\]\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{A\}\], the nodeuuis reachable from some untreated positive, but after removingxx, it is no longer reachable from any untreated positive\. Therefore,xxis the unique untreated positive from whichuuis reachable inℋ​\[𝐕∖𝐀\]\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{A\}\]\. Hence, there exists a directed path fromxxtouuinℋ​\[𝐕∖𝐀\]\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{A\}\]\. Since positive nodes have no incoming edges, all internal vertices on this path must be negative\. Therefore, removing additional positive nodes in𝐁∖𝐀\\mathbf\{B\}\\setminus\\mathbf\{A\}does not affect this path, and it remains present inℋ​\[𝐕∖𝐁\]\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{B\}\]\. Thus,uuis still reachable fromxxinℋ​\[𝐕∖𝐁\]\\mathcal\{H\}\[\\mathbf\{V\}\\setminus\\mathbf\{B\}\], implying thatgℋ,u​\(𝐁\)=1g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\)=1andgℋ,u​\(𝐁∪\{x\}\)=0g\_\{\\mathcal\{H\},u\}\(\\mathbf\{B\}\\cup\\\{x\\\}\)=0, verifying thatgℋ,ug\_\{\\mathcal\{H\},u\}is indeed submodular\. ∎

Before we prove[Theorem˜10](https://arxiv.org/html/2605.20218#Thmtheorem10), we first prove the remaining supporting lemma\.

See[12](https://arxiv.org/html/2605.20218#Thmtheorem12)

###### Proof\.

For a fixed𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}, define random variablesXi=fℋi​\(𝐒\)X\_\{i\}=f\_\{\\mathcal\{H\}\_\{i\}\}\(\\mathbf\{S\}\), fori∈\{1,…,m\}i\\in\\\{1,\\ldots,m\\\}\. We see that these variables are independent and satisfy0≤Xi≤\|𝐍\|0\\leq X\_\{i\}\\leq\|\\mathbf\{N\}\|\. Moreover,𝔼​\[Xi\]=F​\(𝐒\)\\mathbb\{E\}\[X\_\{i\}\]=F\(\\mathbf\{S\}\), andF^m​\(𝐒\)=1m​∑i=1mXi\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)=\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}X\_\{i\}\. Applying Hoeffding’s inequality \(see[Theorem˜1](https://arxiv.org/html/2605.20218#Thmtheorem1)\) yields

Pr⁡\(\|F​\(𝐒\)−F^m​\(𝐒\)\|\>ε\)=Pr⁡\(\|m​F​\(𝐒\)−m​F^m​\(𝐒\)\|\>m​ε\)≤2​exp⁡\(−2​m​ε2\|𝐍\|2\)\\Pr\\left\(\\left\|F\(\\mathbf\{S\}\)\-\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)\\right\|\>\\varepsilon\\right\)=\\Pr\\left\(\\left\|mF\(\\mathbf\{S\}\)\-m\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)\\right\|\>m\\varepsilon\\right\)\\leq 2\\exp\\left\(\-\\frac\{2m\\varepsilon^\{2\}\}\{\|\\mathbf\{N\}\|^\{2\}\}\\right\)Applying a union bound over all possible2\|𝐏\|2^\{\|\\mathbf\{P\}\|\}subsets𝐒⊆𝐏\\mathbf\{S\}\\subseteq\\mathbf\{P\}gives

max𝐒⊆𝐏⁡Pr⁡\(\|F​\(𝐒\)−F^m​\(𝐒\)\|\>ε\)≤2\|𝐏\|\+1​exp⁡\(−2​m​ε2\|𝐍\|2\)\\max\_\{\\mathbf\{S\}\\subseteq\\mathbf\{P\}\}\\Pr\\left\(\\left\|F\(\\mathbf\{S\}\)\-\\hat\{F\}\_\{m\}\(\\mathbf\{S\}\)\\right\|\>\\varepsilon\\right\)\\leq 2^\{\|\\mathbf\{P\}\|\+1\}\\exp\\left\(\-\\frac\{2m\\varepsilon^\{2\}\}\{\|\\mathbf\{N\}\|^\{2\}\}\\right\)The claim follows by plugging inmmas defined in the statement\. ∎

We are now ready to prove[Theorem˜10](https://arxiv.org/html/2605.20218#Thmtheorem10)\.

See[10](https://arxiv.org/html/2605.20218#Thmtheorem10)

###### Proof\.

DefineF^m\\hat\{F\}\_\{m\}as in[Algorithm˜1](https://arxiv.org/html/2605.20218#alg1), where𝐒~\\tilde\{\\mathbf\{S\}\}is an optimizer\. Then, with probability at least1−δ1\-\\delta,

F​\(𝐒^\)\\displaystyle F\(\\hat\{\\mathbf\{S\}\}\)≤F^m​\(𝐒^\)\+ε\\displaystyle\\leq\\hat\{F\}\_\{m\}\(\\hat\{\\mathbf\{S\}\}\)\+\\varepsilon\(By[Lemma12](https://arxiv.org/html/2605.20218#Thmtheorem12)\)≤2​\|𝐏\|⋅F^m​\(𝐒~\)\+ε\\displaystyle\\leq 2\\sqrt\{\|\\mathbf\{P\}\|\}\\cdot\\hat\{F\}\_\{m\}\(\\tilde\{\\mathbf\{S\}\}\)\+\\varepsilon\(By2​\|𝐏\|2\\sqrt\{\|\\mathbf\{P\}\|\}\-approximationMkUalgorithm of\[chlamtac2018densest\]\)≤2​\|𝐏\|⋅F^m​\(𝐒⋆\)\+ε\\displaystyle\\leq 2\\sqrt\{\|\\mathbf\{P\}\|\}\\cdot\\hat\{F\}\_\{m\}\(\\mathbf\{S\}^\{\\star\}\)\+\\varepsilon\(Since𝐒~\\tilde\{\\mathbf\{S\}\}is minimizer forF^m\\hat\{F\}\_\{m\}\)≤2​\|𝐏\|⋅\(F​\(𝐒⋆\)\+ε\)\+ε\\displaystyle\\leq 2\\sqrt\{\|\\mathbf\{P\}\|\}\\cdot\(F\(\\mathbf\{S\}^\{\\star\}\)\+\\varepsilon\)\+\\varepsilon\(By[Lemma12](https://arxiv.org/html/2605.20218#Thmtheorem12)\)≤2​\|𝐏\|⋅F​\(𝐒⋆\)\+ε⋅\(1\+2​\|𝐏\|\)\\displaystyle\\leq 2\\sqrt\{\|\\mathbf\{P\}\|\}\\cdot F\(\\mathbf\{S\}^\{\\star\}\)\+\\varepsilon\\cdot\(1\+2\\sqrt\{\|\\mathbf\{P\}\|\}\)As each invocation of[Lemma˜12](https://arxiv.org/html/2605.20218#Thmtheorem12)fails with probability at mostδ\\delta, union bound tells us that the total failure probability is at most2​δ2\\delta\.

Since the MkU algorithm from\[chlamtac2018densest\]runs in polynomial time and additional steps are polynomial time operations,CASTalso runs in polynomial time\. ∎

## Appendix BImplementation Details

### Dataset Details\.

We examine the HIV, Syphilis, and Hepatitis networks from the ICPSR dataset\. The de\-identified, public\-use dataset can be downloaded at[https://www\.icpsr\.umich\.edu/web/ICPSR/studies/22140](https://www.icpsr.umich.edu/web/ICPSR/studies/22140)after agreeing to the terms and conditions\. These networks contain 778, 542, and 1732 total nodes, of which 88, 44, and 117 are initially infected, respectively\. Each node is associated with a covariate vector with 72 binary dimensions that are one\-hot encoded from 17 categorical variables related to gender, sexual orientation, occupation, etc\.

### Link Prediction for Imperfect Networks\.

For our link prediction modelℓ\\ell, we use an SVM with an RBF kernel\[scikit\-learn\]trained on the other disease network datasets from the ICPSR dataset\. We pass it the cosine similarity between node covariates, the status of each node, an indicator of whether the two nodes share a neighbor, and the size of their shared connected component as features\. We only predict edges between nodes within the same connected component, since the connected components are established in the given forest subgraph\. In practice, keeping all predicted edges in𝒢′\\mathcal\{G\}^\{\\prime\}turns each connected component into a complete graph, so we drop any edges with a predicted probability below a thresholdpℓp\_\{\\ell\}\. We usepℓ=0\.25p\_\{\\ell\}=0\.25in our experiments\.

## Appendix CImperfect Edge Probabilities

For these experiments, the decision graph𝒢′\\mathcal\{G\}^\{\\prime\}has the same topology as the true evaluation graph𝒢\\mathcal\{G\}\. However, edge probabilities in𝒢′\\mathcal\{G\}^\{\\prime\}are drawn from𝒫′\\mathcal\{P\}^\{\\prime\}, an independent and separate distribution from𝒫\\mathcal\{P\}, which is used to generate edge probabilities in𝒢\\mathcal\{G\}\. In the first case that we study, edge probabilities in𝒢′\\mathcal\{G\}^\{\\prime\}are drawn independently but from the same distribution as those in𝒢\\mathcal\{G\}\. In the second case, edge probabilities in𝒢′\\mathcal\{G\}^\{\\prime\}are drawn independently and from a completely different distribution\. We use𝒫′=N​\(0\.75,0\.22\),𝒫=N​\(0\.75,0\.22\)\\mathcal\{P\}^\{\\prime\}=N\(0\.75,0\.2^\{2\}\),\\mathcal\{P\}=N\(0\.75,0\.2^\{2\}\)in the first case and𝒫′=N​\(0\.75,0\.22\),𝒫=U​\(0,1\)\\mathcal\{P\}^\{\\prime\}=N\(0\.75,0\.2^\{2\}\),\\mathcal\{P\}=U\(0,1\)in the second case\. The case where the true edge probabilities are known to the algorithm, i\.e\.,𝒫′=𝒫=N​\(0\.75,0\.22\)\\mathcal\{P\}^\{\\prime\}=\\mathcal\{P\}=N\(0\.75,0\.2^\{2\}\)is also evaluated for reference\. The results across various intervention budgets on the HIV network are shown in[Fig\.˜5](https://arxiv.org/html/2605.20218#A3.F5)\.

![Refer to caption](https://arxiv.org/html/2605.20218v1/results/mismatched-edge-probs.png)Figure 5:Average new infections \(±\\pmSE\) across varying intervention budgets with imperfect edge probabilities\. First, for reference, we show the case where true edge probabilities are known, i\.e\.,𝒫′=𝒫=N​\(0\.75,0\.22\)\\mathcal\{P\}^\{\\prime\}=\\mathcal\{P\}=N\(0\.75,0\.2^\{2\}\)\(left\)\. Then, we study the case where the distribution is known but the decision edge probabilities in𝒢′\\mathcal\{G\}^\{\\prime\}are drawn independently from those in the evaluation graph𝒢\\mathcal\{G\}, i\.e\.,𝒫′=N​\(0\.75,0\.22\),𝒫=N​\(0\.75,0\.22\)\\mathcal\{P\}^\{\\prime\}=N\(0\.75,0\.2^\{2\}\),\\mathcal\{P\}=N\(0\.75,0\.2^\{2\}\)\(middle\)\. Finally, we study the case where the assumed edge probability distribution is mismatched with the true edge probability distribution, i\.e\.,𝒫′=N​\(0\.75,0\.22\),𝒫=U​\(0,1\)\\mathcal\{P\}^\{\\prime\}=N\(0\.75,0\.2^\{2\}\),\\mathcal\{P\}=U\(0,1\)\(right\)\.We observe that empirically, the performance ofCASTremains stable and superior to baseline algorithms in the case where the distribution is known but independently sampled, i\.e\.,𝒫′=N​\(0\.75,0\.22\),𝒫=N​\(0\.75,0\.22\)\\mathcal\{P\}^\{\\prime\}=N\(0\.75,0\.2^\{2\}\),\\mathcal\{P\}=N\(0\.75,0\.2^\{2\}\)\. For example, under the 10% and 20% budgets,CASTonly incurs 0\.879% and 0\.875% more average new infections \(respectively\), compared to the case where the true edge probabilities are known\. For the case of𝒫′=N​\(0\.75,0\.22\),𝒫=U​\(0,1\)\\mathcal\{P\}^\{\\prime\}=N\(0\.75,0\.2^\{2\}\),\\mathcal\{P\}=U\(0,1\), we can compare to the HIV plot in[Fig\.˜3](https://arxiv.org/html/2605.20218#S5.F3), in which the same true edge probabilities were known to algorithms, i\.e\.,𝒫′=𝒫=U​\(0,1\)\\mathcal\{P\}^\{\\prime\}=\\mathcal\{P\}=U\(0,1\)\. Once again,CASThas the best performance across all algorithms\. At 10% and 20% budgets,CASTonly incurs 4\.60% and 0\.430% more average new infections \(respectively\), compared to the case where the true edge probabilities are known from[Fig\.˜3](https://arxiv.org/html/2605.20218#S5.F3)\.

## Appendix DDiscussion

### Broader impact and privacy\.

As public health budgets face increasing strain\[ten2025impact\], resource\-efficient strategies are essential\.CASTaligns with WHO network\-based intervention guidelines\[who\], offering a mathematically rigorous tool for maximizing the impact of every intervention\. However, the sensitive nature of HIV status and transmission data necessitates robust privacy guardrails\. Consequently, any practical application ofCASTmust employ anonymization and secure computational environments to protect these sensitive pieces of information\.

### Ethics and fairness\.

The work that we present here is limited to retrospective simulation studies on disease networks collected in the real world\. There are no human subjects involved\. Before moving beyond simulations, we intend to conduct rigorous testing through pilot studies and field trials to observe algorithmic resource allocation\. These trials will require IRB approvals at all academic institutions involved, and careful, informed consent will be sought from any participants\. We are working very closely with collaborators who have decades of experience in HIV prevention in the field in South Africa, are familiar with real\-world resource allocation challenges, and will ultimately lead any algorithmic trials\. There is one potential ethical consideration that may arise due to the utilitarian objective ofMINT: by prioritizing the prevention of large\-scale infection cascades, one may naturally de\-prioritize individuals in smaller, more isolated components\. While this maximizes the total number of infections averted, it may inadvertently introduce geographic or demographic disparities in resource access\. All of the above considerations will be carefully weighed and discussed with our collaborators\. We will also proceed with appropriate IRB oversight across the different institutions involved\.

### Limitations and future work\.

Our theoretical guarantees and empirical findings are well\-suited to our target setting with a one\-shot intervention\. However, one limitation of theMINTmodel is that it does not capture sequential interventions in which agencies can dynamically update their strategies as budget constraints evolve and the transmission network changes\. Future work could focus on a new model for these adaptive problem instances\. SI may be a more appropriate model of spread for such problems, since it is often used in problems with multiple rounds of interventions, e\.g\.,\[ou2021active\]\. Additionally, investigating fairness\-constrained variants ofMINTthat balance global infection reduction with equitable coverage is also an important direction for future study\.