Dynamic Graph Connectivity Sketches

Connectivity When Edges Arrive and Disappear

A dynamic graph stream inserts and deletes undirected edges while memory is too small to store the full edge set. The goal is to recover a spanning forest: one tree per connected component. Think of islands joined by bridges. When bridges appear or disappear, we do not need every surviving bridge; we need enough certified bridges to connect every island group that remains connected.

Give every edge a canonical identity $e=(\min(u,v),\max(u,v))$. At endpoint $u$ its incidence contribution is $+e$ and at $v$ it is $-e$, where “$e$” means a coordinate in an edge-incidence vector. A deletion applies the opposite update. Linear sketches of all vertex incidence vectors can therefore be added and subtracted without replaying history.

For edges $\{(1,2),(2,3),(3,4)\}$, the cut of component $S=\{1,2\}$ contains only $(2,3)$. Adding sketches for vertices 1 and 2 cancels internal edge $(1,2)$ because its two endpoint signs oppose; $(2,3)$ survives because only endpoint 2 lies in $S$. Sampling a nonzero coordinate of that component sketch produces an outgoing edge.

Incidence vectors encode endpoint-edge relationships. A cutset $\delta(S)$ contains edges with exactly one endpoint in $S$. Hierarchical levels retain edges at geometrically decreasing rates so some level isolates one cut edge. An $L_0$-sampler returns a uniformly random nonzero coordinate or fails with bounded probability. A spanning forest preserves graph connectivity with no cycles. Linearity makes component sketches equal sums of vertex sketches. Dynamic deletions work only when edge identities, orientations, and random seeds are stable.

Cut Sketches and Hierarchical Sampling

Let $x_v$ be the signed edge-incidence vector for vertex $v$. For a component $S$, \[ x_S=\sum_{v\in S}x_v. \] Every internal edge contributes $+1-1=0$; each cut edge contributes exactly one signed nonzero. Because the sampler is linear, $\operatorname{sk}(x_S)=\sum_{v\in S}\operatorname{sk}(x_v)$ is an $L_0$-sampling sketch of the component cut.

At level $j$, retain edge $e$ when a stable hash falls below probability $2^{-j}$. If a cut has size $s$, a level with inclusion probability near $1/s$ contains exactly one cut edge with constant probability: \[ \Pr[\text{one survivor}]=sp(1-p)^{s-1}=\Theta(1). \] One-sparse moments recover and fingerprint that edge. Independent repetitions reduce failure to $\delta$. The proof obligations are stable canonical edge encoding, linear turnstile updates, sufficient hash independence, valid field/counter ranges, and randomness hidden from a nonadaptive stream.

Summing component sketches must use a snapshot of the current forest partition. A sampled edge is checked against the current disjoint-set structure; self-loops after contraction are discarded. Parallel Borůvka proposals require cycle-safe union operations. Small levels cover large cuts; dense levels cover small cuts.

flowchart TD
 A[Canonical signed endpoint updates] --> B[Linear sketch at every vertex]
 B --> C[Sum sketches over current component]
 C --> D[Internal edges cancel]
 D --> E[Cut incidence vector remains]
 E --> F[Geometric levels isolate one cut edge]
 F --> G[Fingerprint verifies candidate]
 G --> H[Live outgoing edge merges components]
 H --> I[Repeat Boruvka rounds]
 A --> J{Encoding seed or arithmetic invalid?}
 J -->|yes| K[Cancellation or certificate fails]
 J -->|no| B
 classDef navy fill:#17365D,color:#fff,stroke:#17365D;
 classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
 classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
 classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
 class A,B,C,D navy;
 class E,F,G,I purple;
 class H teal;
 class J,K crimson;

Recovering a Spanning Forest

Begin with each vertex as its own component. In one Borůvka round, query repeated cut sketches for each component, propose one verified outgoing edge, and union endpoints when they currently belong to different components. If every non-isolated component finds an edge, the number of components falls by a constant factor; $O(\log n)$ rounds suffice. Multiple independent recovery structures or carefully scheduled levels support all rounds with an overall failure budget.

from collections import defaultdict, deque

def canonical(u, v):
    if u == v:
        raise ValueError("self-loop not allowed")
    return (u, v) if u < v else (v, u)

class DynamicGraphOracle:
    def __init__(self, vertices):
        if vertices < 1:
            raise ValueError("positive vertex count required")
        self.n = vertices
        self.counts = defaultdict(int)

    def update(self, u, v, delta):
        if not (0 <= u < self.n and 0 <= v < self.n):
            raise ValueError("vertex outside universe")
        if delta not in (-1, 1):
            raise ValueError("unit turnstile update required")
        e = canonical(u, v)
        nxt = self.counts[e] + delta
        if nxt not in (0, 1):
            raise ValueError("strict dynamic graph violated")
        self.counts[e] = nxt

    def live_edges(self):
        return sorted(e for e, count in self.counts.items() if count)

    def spanning_forest(self):
        parent = list(range(self.n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        forest = []
        for u, v in self.live_edges():
            a, b = find(u), find(v)
            if a != b:
                parent[b] = a
                forest.append((u, v))
        return forest

    def connected(self, source, target, edges=None):
        adj = [[] for _ in range(self.n)]
        for u, v in self.live_edges() if edges is None else edges:
            adj[u].append(v); adj[v].append(u)
        seen, q = {source}, deque([source])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in seen:
                    seen.add(v); q.append(v)
        return target in seen

g = DynamicGraphOracle(6)
for edge in [(0,1),(1,2),(0,2),(2,3),(3,4)]:
    g.update(*edge, 1)
forest = g.spanning_forest()
assert len(forest) == 4 and g.connected(0, 4, forest)
g.update(2, 3, -1)
forest_after = g.spanning_forest()
assert not g.connected(0, 4)
assert len(forest_after) == 3

empty = DynamicGraphOracle(3)
assert empty.spanning_forest() == []
try:
    empty.update(0, 0, 1)
    raise AssertionError("self-loop accepted")
except ValueError:
    pass
try:
    empty.update(0, 1, -1)
    raise AssertionError("invalid deletion accepted")
except ValueError:
    pass

print("forest before deletion:", forest)
print("forest after bridge deletion:", forest_after)

Dynamic Networks Under Failures

In a teaching case, enumerate every cut of a six-vertex graph and compare exact cut edges with summed incidence vectors. In professional network telemetry, edge coordinates may represent canonical device links; sketches from collectors merge only when universe, orientation, field, levels, repetitions, and seeds match. In an adversarial service, public seeds let clients engineer collisions, so the nonadaptive theorem no longer applies.

Invalidating evidence includes returned deleted edges, failure to cancel internal edges, forest edges forming cycles, disagreement with exact sampled audits, excessive sampler FAIL rate, arithmetic wraparound, duplicate/malformed updates, or connectivity errors concentrated on small bridge cuts.

flowchart TD
 A[Define graph and update contract] --> B[Canonicalize edge identities]
 B --> C[Choose levels repetitions and failure budget]
 C --> D[Validate against exact dynamic graph]
 D --> E{Forest validity and recall pass?}
 E -->|yes| F[Deploy versioned sketches]
 E -->|no| G[Resize strengthen or reject]
 F --> H[Monitor deleted edges cycles and FAIL rate]
 H --> I{Threat model unchanged?}
 I -->|yes| H
 I -->|no| G
 classDef navy fill:#17365D,color:#fff,stroke:#17365D;
 classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
 classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
 classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
 class A,B,C navy;
 class D,F purple;
 class E,H teal;
 class G,I crimson;

Trace a Connectivity Recovery

Connectivity recovery is a composition of invariants: signed incidence cancellation, valid $L_0$ certificates, and cycle-safe forest contraction.