Contact Tracing

When a pathogen spreads from person to person, it follows a path through a contact network — a graph whose nodes are people and whose edges are close interactions. Every new infection adds a branch to a growing tree of transmission chains.

Contact tracing is the algorithmic countermeasure: work backwards from each diagnosed case, find the people who were recently exposed, and isolate them before they spread the disease further. Done fast enough, the strategy cuts the branches before they can branch again.

The mathematical concept behind it is the basic reproduction number $R_0$ (R-naught): the average number of new infections one case produces in a fully susceptible population. If tracing reduces the effective $R$ below 1, each generation of infections shrinks. If it cannot keep up, the chain grows exponentially and the outbreak escapes.

Whether tracing can keep up depends on speed, coverage, and the shape of the contact graph — and this is where computer science enters the picture. Related ideas appear throughout the study of graph algorithms and network reachability.

Below is a small contact network. One person is infected (red). Each day the disease spreads to their contacts; at the same time, the tracing algorithm tries to find and quarantine exposed nodes before they infect others.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{lbl_speed}} <input type="range" id="speed" min="0" max="100" value="50">
    <span id="speed-val">50%</span></label>
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="480" height="280"></canvas>
<div class="stats">
  <span id="stat-day">{{lbl_day}} 0</span> &nbsp;|&nbsp;
  <span id="stat-infected">{{lbl_infected}} 1</span> &nbsp;|&nbsp;
  <span id="stat-quarantined">{{lbl_quarantined}} 0</span> &nbsp;|&nbsp;
  <span id="stat-r">R&#x2091;&#x200B;&#x2071;&#x2071; ~1.00</span>
</div>
<div id="status" class="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap;
            margin-bottom: .5rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 100px; }
button { font: 600 13px system-ui; padding: .35rem .75rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border-radius: 8px; background: #f4f7fa;
         width: 100%; max-width: 480px; }
.stats { font-size: .8rem; color: #555; margin: .45rem 0; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; }
.status.win { color: #0a7d33; }
.status.lose { color: #c92f3c; }

// Code not found

Slide Tracing speed all the way left and the outbreak grows unchecked — each generation roughly doubles. Move it right and you can see the effective $R$ drop below 1 as the algorithm isolates branches before they propagate. The race between viral spread and algorithmic tracing is exactly what public-health modellers study.

Underneath the public-health language, contact tracing is breadth-first search (BFS) racing against exponential growth.

• The graph model. People are nodes; a sufficiently close contact during the infectious period is an edge. An infection event is a directed edge from infector to infectee. Tracing walks the reverse edges from a diagnosed node to find everyone at risk.
• The race condition. BFS on a sparse graph runs in $O(V + E)$ time. Exponential growth, however, doubles the frontier every generation interval. Tracing wins only if it can visit and quarantine each at-risk node before that node's own infectious period begins.
• Coverage gaps matter. If a fraction $p$ of contacts are missed (people not reached, asymptomatic cases unknown), the effective reproduction number becomes roughly $R_{\text{eff}} \approx R_0 \cdot (1 - p \cdot e)$, where $e$ is tracing efficacy. Even small gaps compound across generations.
• Network hubs are critical. In a real contact graph, degree is highly heterogeneous — a few "super-spreader" nodes have many contacts. Missing a hub in tracing can unleash an entire sub-cluster. Graph centrality measures (degree, betweenness) predict which nodes most urgently need to be reached.
• Notification delay is the enemy. A delay of even one generation interval between symptom onset and completed tracing can let $R_{\text{eff}}$ stay above 1 even with otherwise perfect coverage.

The 2020 Science paper by Ferretti et al. quantified these factors for SARS-CoV-2 and showed that only digital tracing — using smartphone proximity logs to notify contacts within hours — could be fast enough to suppress the outbreak without full lockdown.

"Find everything reachable from a source before it spreads further" is a recurring shape in computer science:

• Malware propagation analysis. Security teams trace how a piece of malware moved laterally through a corporate network — the same BFS walk on a host-connection graph, the same race against dwell time.
• Network fault isolation. When a router fails, engineers trace which downstream nodes lost connectivity. The contact-tracing logic (walk the graph, mark affected nodes, isolate them) maps directly.
• Supply-chain disruption. A single failed supplier can cascade through a dependency graph. Tracing the reachability set predicts which products are at risk.
• Influence maximization. In social networks, choosing the $k$ nodes whose activation reaches the most others is the dual of contact tracing — you want maximum spread rather than minimum. Both require understanding graph reachability.
• Privacy-preserving tracing. The COVID-19 era produced cryptographic protocols (Apple/Google Exposure Notification, DP-3T) that compute contact-graph reachability without revealing individual identities — a remarkable marriage of epidemiology and computational complexity.

Every outbreak is a reachability problem: can you visit and neutralize each newly exposed node before it creates more? When the answer is yes, the epidemic shrinks. When the answer is no, it grows exponentially — and no amount of effort applied after the fact recovers the lost ground.

The same race between "find the spread" and "let it propagate" appears in malware containment, fault isolation, and network influence. Contact tracing turned a public-health intervention into a computer-science lesson: speed and coverage on a graph are not soft targets — they are the difference between suppression and runaway growth. Understanding graph algorithms is, quite literally, a matter of life and death.