Introduction

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 R0R_0 (R-naught): the average number of new infections one case produces in a fully susceptible population. If tracing reduces the effective RR 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.

Try It: Bend the Curve

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.

<!-- HTML layout: controls, canvas for the network graph, and stats bar -->
<div class="controls">
  <label>Tracing 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">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<canvas id="canvas" width="480" height="280"></canvas>
<div class="stats">
  <span id="stat-day">Day 0</span> &nbsp;|&nbsp;
  <span id="stat-infected">Infected: 1</span> &nbsp;|&nbsp;
  <span id="stat-quarantined">Quarantined: 0</span> &nbsp;|&nbsp;
  <span id="stat-r">R&#x2091;&#x200B;&#x2071;&#x2071; ~1.00</span>
</div>
<div id="status" class="status"></div>

/* Styles: controls row, canvas, stats, status message */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Simulation of an outbreak on a small contact network with configurable tracing speed */

/* 8-node contact network (nodes A-H) with fixed positions on the canvas */
const NODES = [
  { id: 0, x: 60,  y: 140, label: 'A' },
  { id: 1, x: 150, y: 60,  label: 'B' },
  { id: 2, x: 150, y: 220, label: 'C' },
  { id: 3, x: 260, y: 100, label: 'D' },
  { id: 4, x: 260, y: 180, label: 'E' },
  { id: 5, x: 370, y: 60,  label: 'F' },
  { id: 6, x: 370, y: 180, label: 'G' },
  { id: 7, x: 440, y: 120, label: 'H' },
];
const EDGES = [
  [0,1],[0,2],[1,3],[2,4],[3,4],[3,5],[4,6],[5,7],[6,7]
];

/* Build adjacency list from edge list */
const adj = Array.from({ length: NODES.length }, () => []);
for (const [a, b] of EDGES) { adj[a].push(b); adj[b].push(a); }

/* Node status constants */
const STATE_SUSCEPTIBLE  = 'S';
const STATE_INFECTED     = 'I';
const STATE_QUARANTINED  = 'Q';
const STATE_RECOVERED    = 'R';

let state, day, running, timer;

function initState() {
  /* Initialize every node; node 0 (A) starts infected */
  state = NODES.map((_, i) => ({
    status: i === 0 ? STATE_INFECTED : STATE_SUSCEPTIBLE,
    infectedDay: i === 0 ? 0 : -1,
    traced: false,
  }));
  day = 0;
  running = false;
  clearTimeout(timer);
  updateStats();
  draw();
  document.getElementById('status').textContent = '';
  document.getElementById('status').className = 'status';
}

function getSpeed() {
  return parseInt(document.getElementById('speed').value, 10) / 100;
}

/* Advance the simulation by one day: spread, trace, recover */
function step() {
  if (isOver()) return;
  day++;

  /* Spread: every infected node may infect susceptible neighbors */
  const newlyInfected = [];
  for (let i = 0; i < NODES.length; i++) {
    if (state[i].status !== STATE_INFECTED) continue;
    for (const j of adj[i]) {
      if (state[j].status === STATE_SUSCEPTIBLE) {
        newlyInfected.push(j);
      }
    }
  }
  for (const j of newlyInfected) {
    state[j].status = STATE_INFECTED;
    state[j].infectedDay = day;
  }

  /* Trace: each infected node is quarantined with probability = speed */
  const speed = getSpeed();
  for (let i = 0; i < NODES.length; i++) {
    if (state[i].status !== STATE_INFECTED) continue;
    /* Higher slider value = faster tracing */
    if (Math.random() < speed) {
      state[i].status = STATE_QUARANTINED;
      state[i].traced = true;
      /* Also quarantine susceptible neighbors with same probability */
      for (const j of adj[i]) {
        if (state[j].status === STATE_SUSCEPTIBLE && Math.random() < speed) {
          state[j].status = STATE_QUARANTINED;
          state[j].traced = true;
        }
      }
    }
  }

  /* Recover: infected nodes recover after 3 days */
  for (let i = 0; i < NODES.length; i++) {
    if (state[i].status === STATE_INFECTED && day - state[i].infectedDay >= 3) {
      state[i].status = STATE_RECOVERED;
    }
  }

  updateStats();
  draw();

  if (isOver()) {
    endMessage();
    running = false;
  } else if (running) {
    timer = setTimeout(step, 900);
  }
}

function isOver() {
  return state.every(s =>
    s.status === STATE_QUARANTINED ||
    s.status === STATE_RECOVERED   ||
    s.status === STATE_SUSCEPTIBLE
  );
}

/* Rough effective R estimate: current infected / newly infected yesterday */
function estimateReff() {
  const infected = state.filter(s => s.status === STATE_INFECTED).length;
  const prev = state.filter(s => s.infectedDay === day - 1 && s.status === STATE_INFECTED).length || 1;
  return (infected / prev).toFixed(2);
}

function updateStats() {
  const infected    = state.filter(s => s.status === STATE_INFECTED).length;
  const quarantined = state.filter(s => s.status === STATE_QUARANTINED).length;
  document.getElementById('stat-day').textContent =
    'Day ' + day;
  document.getElementById('stat-infected').textContent =
    'Infected: ' + infected;
  document.getElementById('stat-quarantined').textContent =
    'Quarantined: ' + quarantined;
  document.getElementById('stat-r').textContent =
    'Rₑ​ⁱⁱ ~' + estimateReff();
}

/* Render the contact network on the canvas */
function draw() {
  const canvas = document.getElementById('canvas');
  const ctx    = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  /* Draw edges first (behind nodes) */
  ctx.strokeStyle = '#cdd5df';
  ctx.lineWidth = 1.5;
  for (const [a, b] of EDGES) {
    ctx.beginPath();
    ctx.moveTo(NODES[a].x, NODES[a].y);
    ctx.lineTo(NODES[b].x, NODES[b].y);
    ctx.stroke();
  }

  /* Draw each node with color reflecting its status */
  const COLOR = {
    [STATE_SUSCEPTIBLE]:  '#a8d4f5',
    [STATE_INFECTED]:     '#e63946',
    [STATE_QUARANTINED]:  '#f4a261',
    [STATE_RECOVERED]:    '#57cc99',
  };
  for (const n of NODES) {
    const s = state[n.id];
    ctx.beginPath();
    ctx.arc(n.x, n.y, 18, 0, 2 * Math.PI);
    ctx.fillStyle   = COLOR[s.status];
    ctx.fill();
    ctx.strokeStyle = '#444';
    ctx.lineWidth   = 1.5;
    ctx.stroke();

    ctx.fillStyle  = '#111';
    ctx.font       = 'bold 13px system-ui, sans-serif';
    ctx.textAlign  = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(n.label, n.x, n.y);
  }

  /* Legend at the bottom of the canvas */
  const legend = [
    { color: '#a8d4f5', label: 'Susceptible' },
    { color: '#e63946', label: 'Infected' },
    { color: '#f4a261', label: 'Quarantined' },
    { color: '#57cc99', label: 'Recovered' },
  ];
  let lx = 8, ly = H - 22;
  ctx.font = '11px system-ui, sans-serif';
  ctx.textBaseline = 'middle';
  for (const { color, label } of legend) {
    ctx.fillStyle = color;
    ctx.fillRect(lx, ly - 6, 12, 12);
    ctx.strokeStyle = '#666';
    ctx.lineWidth = .8;
    ctx.strokeRect(lx, ly - 6, 12, 12);
    ctx.fillStyle = '#333';
    ctx.textAlign = 'left';
    ctx.fillText(label, lx + 15, ly);
    lx += ctx.measureText(label).width + 28;
  }
}

function endMessage() {
  const active = state.filter(s => s.status === STATE_INFECTED).length;
  const el = document.getElementById('status');
  if (active === 0) {
    const total = state.filter(s => s.status === STATE_RECOVERED || s.status === STATE_QUARANTINED).length;
    el.textContent = i18nFmt('Outbreak controlled — %total% nodes affected total.', { total });
    el.className = 'status win';
  } else {
    el.textContent = 'Outbreak escaped — tracing was too slow.';
    el.className = 'status lose';
  }
}

document.getElementById('btn-step').addEventListener('click', () => {
  running = false; clearTimeout(timer); step();
});
document.getElementById('btn-run').addEventListener('click', () => {
  if (isOver()) return;
  running = true; step();
});
document.getElementById('btn-reset').addEventListener('click', initState);
document.getElementById('speed').addEventListener('input', function () {
  document.getElementById('speed-val').textContent = this.value + '%';
});

initState();
Result
Console

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 RR 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.

The Real Complexity

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)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 pp of contacts are missed (people not reached, asymptomatic cases unknown), the effective reproduction number becomes roughly Reff≈R0⋅(1−p⋅e)R_{\text{eff}} \approx R_0 \cdot (1 - p \cdot e), where ee 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 ReffR_{\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.

Where It Matters

"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 kk 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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/digital-contact-tracing/Content licensed under CC BY-NC 4.0.