INTRODUCTION

Contact tracing followed by isolation is one of the most effective ways to control epidemics caused by infectious diseases. In this intervention strategy, contact tracers ask infected individuals to report their recent contacts; they then trace these contacts, asking them to isolate for a period of time [5]. Recently, technologies such as the Google-Apple app [1] have provided a solution to augment human contact tracers. When contact tracing apps are used, the strategy is called digital contact tracing; otherwise, it is called manual contact tracing.

The main limitation of contact tracing is the number of individuals who can be asked to isolate; this number is constrained since isolation imposes a significant economic and social burden to the population. For manual contact tracing, the budget is also dependent on the economic cost of hiring contact tracers. From these constraints, we can see a trade-off between reducing infection spread and minimizing socioeconomic costs. This brings forth a natural question that we study: which individuals should we isolate to make the most effective use of the budget for contact tracing?

Our contributions. We use a Markov Decision Process (MDP) framework to formulate the problem of reducing the size of an outbreak through efficient contact tracing while limiting the number of isolations. At each timestep, the policymaker wants to choose a set of nodes that, when asked to quarantine, minimizes the (expected) number of infections at the end of the epidemic. Since the disease dynamics are constantly changing (due to fluctuating attitudes and behavior), we will only consider finite time horizons of the MDP by solving the combinatorial problem, MinExposed, which focuses on the second neighborhood of the infected set.

• We prove that MinExposed is NP-Hard, so we develop an LP-based algorithm with rigorous approximation guarantees. Using insights from the previous algorithm, we introduce an interpretable and practical greedy approximation algorithm. • Based on our theoretical results, we devise a heuristic which requires minimal information of the contact graph or disease model, and thus can be made operational in the real world. • We run simulations of an epidemic with realistic contact networks and parameter values to assess the performance of our heuristic-the results suggest that the heuristic successfully bends the epidemic curve.

PRELIMINARIES

Let 𝐺 = (𝑉 , 𝐸) be the social contact network and let the disease spread on 𝐺 by an SIR type diffusion process [7]: at each timestep 𝑡, an infected node 𝑢 ∈ 𝐼 (𝑡) transmits the disease to each of their neighbors 𝑣 independently with probability 𝑞 𝑢𝑣 . We assume the currently infected nodes, 𝐼 = 𝐼 (𝑡), are known to the policymaker and will self-isolate until they recover. Though all previously infected nodes self-isolate, neighbors of 𝐼 , which we denote 𝑉 1 = 𝑁 𝐺 (𝐼 ) -𝐼 , are already exposed and can continue to spread the disease to the rest of the graph. Policymakers must contact trace these individuals and ask them to isolate. Since this process is expensive and timeintensive for both the government and quarantined individuals, we let 𝐵 be the budget on the number of nodes that can be reached.

Given this, the objective of policymakers is to minimize the total number of infections in 𝐺 at the end of the epidemic. This is an idealized problem to solve since the contact graph, transmission rates, and compliance rates are all constantly changing due to various forms of social distancing. As a result, we focus on locally optimal solutions which minimize the expected number of infections in the second neighborhood of 𝐼 . We denote this neighborhood as 𝑉 2 = 𝑁 𝐺 (𝑉 1 ) -𝐼 -𝑉 1 and formalize the problem below.

The MinExposed Problem: Given contact graph 𝐺 = (𝑉 , 𝐸), a subset 𝐼 ⊆ 𝑉 of infected nodes, transmission probabilities 𝑞 𝑢𝑣 for (𝑢, 𝑣) ∈ 𝐸, and a budget 𝐵, the objective is to find a subset 𝑄 ⊆ 𝑉 1 satisfying |𝑄 | ≤ 𝐵 to quarantine which minimizes the expected number of infections in 𝑉 2 . In our full paper [6], we also consider the possibility of non-compliance when asked to quarantine.

OUR APPROACH

In this section, we present our two algorithms; we defer the proofs of their approximation guarantees and the hardness of MinExposed to our full paper [6]. There, we also show how our methods can be extended to guarantee demographic fairness, both with respect to the people quarantined and the expected number of total infections.

DepRound

We write MinExposed as a mixed-integer linear program (MILP):

We have 𝑥 𝑢 , 𝑦 𝑢 for 𝑢 ∈ 𝑉 1 as indicators representing 𝑢 being quarantined and 𝑢 potentially spreading the disease, respectively. We allow at most 𝐵 nodes to be quarantined, as indicated by Constraint 1. Finally, 𝑧 𝑣 for 𝑣 ∈ 𝑉 2 represents a lower bound on the probability of 𝑣 getting infected, as conveyed through Constraint 2.

Algorithm 1 DepRound 1: Relax the integer constraints of the MILP to obtain an LP 2: Solve the LP to get vectors 𝑥, 𝑦 ∈ [0, 1] 𝑉 1 3: Apply [8] to round vector

DegGreedy

In the analysis of DepRound (see [6]), we used the union bound to give an upper bound on the objective value of MinExposed.

We now show a simple and interpretable greedy algorithm that directly minimizes the upper bound, and hence gives the same approximation guarantee as DepRound.

Algorithm 2 DegGreedy

1: 𝑤 𝑢 ← 𝑝 𝑢 • 𝑣 ∈𝑉 2 ,(𝑢,𝑣) ∈𝐸 𝑞 𝑢𝑣 for 𝑢 ∈ 𝑉 1 2: pick 𝐵 nodes with the highest 𝑤 𝑢 values in 𝑉 1 to be in 𝑄

COMPUTATIONAL EXPERIMENTS

We report on computational experiments conducted to assess the performance of our algorithms. To do this, we use realistic representation of the underlying social network and the disease dynamics.

Disease model. We assume a simple SIR model, with a two-timestep recovery. At each timestep, we have a susceptible set (𝑆), infected set (𝐼 = 𝐼 1 ∪𝐼 2 ), and a recovered set (𝑅). The partitioning of 𝐼 models incomplete information: 𝐼 1 is the set of recently infected nodes not yet known to be transmitting the disease (due to the incubation period and wait time testing). By the next timestep, 𝐼 1 has been tested and becomes 𝐼 2 , which is known to the policymaker. As a result, all quarantine decisions will be based only on 𝐼 2 .

Algorithms to compare. In our full paper [6], we devised a practical and implementable variant of DegGreedy, which we called Private DegGreedy. Here, we compare it with two intuitive baselines studied in Armbruster and Brandeau [2]: MostNamed and ListLength. The MostNamed policy selects nodes in 𝑉 1 with the most infected neighbors and the ListLength policy is similar, but weighs each neighbor by the inverse of their degree.

Social contact networks. We use a realistic synthetic social contact network for Montgomery County in Virginia constructed by a first principles approach by Barrett et al. [3] and Eubank et al. [4].

For details on the networks and disease model parameters such as transmission probabilities and budget, see our full paper [6]. Figure 1 shows the effect of the algorithms on the epidemic trajectory. As can be noted the method bends the epidemic curve by (𝑖) reducing the total number of infections, (𝑖𝑖) delaying the peak, and (𝑖𝑖𝑖) reducing the size of the peak. The latter two are especially important in practice: a later peak enables time for developing vaccines, which can potentially stop the infection before the peak, and having a smaller peak ensures that people are able to receive adequate treatment in hospitals, which have limited capacity.