---
# System prepended metadata

title: Lecture 6 - Dynamic Connectivity
tags: [Algorithm]

---

# Lecture 6 - Dynamic Connectivity

###### tags: `Algorithm`

## Fully Dynamic Connectivity
### Dynamic Model
We can $Insert$ or $Delete$ edges in this graph, and still find the connectivity of any pair of vertices
![](https://i.imgur.com/IE0uCoG.png)
### Challenge: Why Dynamic Forest didn’t Solve It 
+ In a forest, a $Link$ connects two distinct trees. In a general graph, the endpoints of an **inserted edge** might already be connected
+ In a forest, a $Cut$ splits one tree into two. In a general graph, an **edge deletion** might not change connectivity
+ In a forest, there is a unique path between any two nodes in each tree. In a general graph, there can be many
### Idea: Maintaining the Spanning Forest of $G$
+ Spanning forest $F$: there is a spanning tree in each **connected component**
+ Connectivity: check whether $u$, $v$ are in the same spanning tree of $F$
    ![](https://i.imgur.com/N8QLHln.png)
+ $Insert(u,v)$
    + When $u$, $v$ are in the same tree, $F$ do not change
    + When $u$, $v$ are not in the same tree, connect these trees to a bigger tree
+ $Delete(u,v)$
    + The tree will be split into two parts
    + We need to find other edges reconnecting these two parts
    ![](https://i.imgur.com/0zQMVCt.png)
    + **However, enumerating edges will be time consuming**
    ![](https://i.imgur.com/d5yhe8d.png)
### *Holm, Lichtenberg & Thorup*’s structure
+ $O(\log^2n)$ amortized update time 
+ Best deterministic amortized update time so far
+ Appears in STOC’98
#### High-Level Description
+ Each edge $e$ is assigned a level $\ell(e)$ ($0≤\ell(e)≤\ell_{\max}$)
+ $E_i=\{e\in E|\ell(e)\geq i\}$
+ So $E=E_0\supseteq E_1\supseteq ...\supseteq E_{\ell_{\max}}$
    ![](https://i.imgur.com/ssA83jh.png)
+ We keep the set of spanning forest $F=F_0\supseteq F_1\supseteq ...\supseteq F_{\ell_{\max}}$ on $E_0,E_1,...,E_{\ell_{\max}}$
    ![](https://i.imgur.com/lENGTNl.png)
    + If $e=(u,v)$ is a non-tree edge in $E_i$, $u$ and $v$ are connected in $F_i$
    + If $e$ is a tree edge in $F_i$, it must be tree edge in $F_j$ ($j<i$)
    ![](https://i.imgur.com/Eymo77j.png)
+ Also, the number of vertices of a tree in $F_i$ is at most $n/2^i$ 
    + The sizes of connected components decrease by a half when level increases 
    + So $\ell_{\max}=O(\log n)$
+ **These properties are maintained throughout the algorithm**
#### Algorithm
+ Initially the graph is empty
+ Level of an edge only increases, never decreases 
    + When we have checked the edge, its level increases
    + Only increases for $\ell_{\max}=O(\log n)$ times 
    + So the amortized time for an edge is small
+ $Insert(e)$
    + $\ell(e)=0$
    + If its two ends are not connected in $F_0$, $e$ is added to $F_0$ 
+ $Delete(e)$
    + If $e$ is not a tree edge at level $\ell(e)$, simply delete $e$ 
    + If $e$ is a tree edge, delete it in $F_0,F_1,...,F_{\ell(e)}$, and call $Reconnect(e, \ell(e))$
    ![](https://i.imgur.com/rr0nooT.png)
    :::info
    Spanning forests $F=F_0\supseteq F_1\supseteq ...\supseteq F_{\ell_{\max}}$ on $E_0,E_1,...,E_{\ell_{\max}}$ 
    So when $e$ is not a tree edge at level $\ell(e)$, it can not be a tree edge at other levels
    :::
+ $Reconnect((u,v),i)$: reconnect trees containing $u$ and $v$ by edges of level $i$
    + $T$: original tree containing $(u,v)$
    + $T(u),T(v)$: trees containing $u$, $v$ after deletion of $(u,v)$
    + One of $T(u)$, $T(v)$ has at most a half as many vertices as $T$, assume it is $T(u)$, move $T(u)$ to level $i+1$
        ![](https://i.imgur.com/BD91qgy.png)
    + Check level $i$ edges $f$ incident to $T(u)$ one by one, either
        + $f$ does not connect $T(u)$ and $T(v)$, then it must be included within $T(u)$, increase its level to $i+1$
            ![](https://i.imgur.com/TRgq8jZ.png)
        + $f$ connect $T(u)$ and $T(v)$, stop the search, and add $f$ to $F_0$, $F_1$,...,$F_i$
            ![](https://i.imgur.com/SGP61bE.png)
            + If no such edges are found, call $Reconnect((u,v),i-1)$
            + If $i=0$, we conclude that there is no reconnecting edges
+ For example
    + $F_0, F_1, F_2$: (non-tree edges are only in their levels)
        ![](https://i.imgur.com/7167vsG.png)
    + Deleting a tree edge
        ![](https://i.imgur.com/HOwzASU.png)
    + Call $Reconnect(e, \ell(e))$
        ![](https://i.imgur.com/liQNFjR.png)
    + Check for an edge whether it can reconnect them
        ![](https://i.imgur.com/k508VbF.png)
    + Remove it to higher level
        ![](https://i.imgur.com/FhB1DaK.png)
    + Call reconnect in lower level
        ![](https://i.imgur.com/YQNUMc4.png)
#### Analysis
+ Update time: $O(\log^2 n)$ (amortized)
    + In one update we may need to check all the edges associated with a subtree $T(u)$
    + But after checking an edge, its level must increase, so every edge can be checked $O(\log n)$ times
    + If initially the graph is empty, the number of edges is at most the number of updates, so we need to check $O(\log n)$ edges per update
    + Since merging two trees takes $O(\log n)$ time, and an edge can merge trees in $O(\log n)$ levels, so the amortized update time is $O(\log^2n)$
    + $Delete$ can cost $O(\log^2n)$ time
+ Query time: $O(\log n)$ (actually, it can be done in $O(\log n/\log \log n)$)
+ Space: $O(m+n\log n)$ (almost linear)
### Summary
+ (Deterministic, Amortized): $O(\log^2n)$ [HDLT01]
+ (Randomized, Amortized): $O(\log n(\log \log n)^2)$ [HHKP17]
+ (Randomized, Worst-Case, None-Adaptive): $O(\log^4n)$ [KKM13, Wan15, GKKT15]
+ (Randomized, Worst-Case, Adaptive, Monte-Carlo): $O(n^{0.4+o(1)})$ [NS16]
+ (Randomized, Worst-Case, Adaptive, Las-Vegas): $O(n^{0.49305+o(1)})$ [NS16]
+ (Deterministic, Worst-Case): $O(\sqrt{\frac{n(\log \log n)^2}{\log n}})$ [KRKPT15]
## Dynamic Subgraph Connectivity
### Dynamic Subgraph Model 
+ There is a fixed underlying graph $G$
+ Every vertex in $G$ is in one of the two states $on$ and $off$
+ Construct a dynamic data structure
    + $Update$: switch a vertex $on$ or $off$
    + $Query$: for a pair $(u,v)$, answer connectivity/shortest path between $u$ and $v$ in the subgraph of $G$ induced by the $on$ vertices
    ![](https://i.imgur.com/6oBZMgu.png)
+ Dynamic subgraph connectivity with $\tilde O(m^{2/3})$ amortized update time and $\tilde O(m^{1/3})$ query time
    + *Dynamic Connectivity: Connecting to Networks and Geometry* 
    + By *Chan, Pâtraşcu & Roditty ‘2008*
+ Do not maintain a spanning forest for the whole graph
### Trivial Algorithm 
+ Since a vertex can associate with at most $n-1$ edges, so by the edge connectivity structure, we can get a vertex connectivity structure of amortized update time $\tilde O(n)$ and query time $\tilde O(1)$
+ We want sublinear update time structures
### Preprocessing
+ Maintain two sets of $on$ vertices: $P$, $Q$
    + Initially all $on$ vertices are in $P$
    + We only $Delete$ vertices from $P$
    + When we turn a vertex $on$, we $Insert$ it into $Q$
+ Thus
    + $P$ just supports $Delete$ (**decremental structure**)
    + $Q$ supports both $Insert$ and $Delete$
+ Reinitialize after $q=m^{2/3}$ $Update$s
+ So the size of $Q$ is at most $m^{2/3}$
#### High and Low Components
+ Maintain the decremental connectivity structure with edge updates in $P$
+ For a connected component in $P$, if the sum of its degrees exceeds $m^{1/3}$, it is called a **high component**, otherwise it is a **low component**
+ The number of high components is bounded by $O(m/m^{1/3})=O(m^{2/3})$
![](https://i.imgur.com/04fmcYZ.png)
#### The Edge Set $\Gamma$
+ We construct a edge set $\Gamma$ **on the vertices in $G$**
+ If both $u$ and $v$ are adjacent to the same low component in $P$, then there is an edge $(u,v)$ in $\Gamma$
+ There can be multiple edges between $u$ and $v$
    ![](https://i.imgur.com/Qvl4SEs.png)
+ For every edge connecting a low component and a vertex, since the number of edges associate with that low component is at most $m^{1/3}$, so the number of edges in $\Gamma$ generated by this edge is at most $m^{1/3}$
    ![](https://i.imgur.com/R6X66ve.png)

+ So the total number of edges in $\Gamma$ is at most $m\times m^{1/3}=m^{4/3}$
#### Maintain a New Graph
+ Maintain a graph $G^*$ of vertices $O(m^{2/3})$
    + Vertices of $Q$
    + Vertices set $H$ where each vertex represents a high component in $P$
    + And the original edges in $G$ connecting those vertices and components
    + Include the edges of $\Gamma$ into $G^*$
+ It is easy to check that for every pair of active vertices in $Q$, they are connected in $G$ iff they are connected in $G^*$
    ![](https://i.imgur.com/qj9aCHr.png)
### Query
+ It takes $O(\log n)$ time to find a vertex in $Q$ which component it is in
+ For vertices in high components
    + Find the vertex in $G^*$ which represents that component
+ For vertices in low components
    + Search for an active vertex of $Q$ adjacent to the component
    + If it does not exist, the component is isolated
    + Query time: $\tilde O(m^{1/3})$, since the edges associated with a low component is $O(m^{1/3})$
### Analysis
#### Preprocessing Time
+ Initializing $G^*$ and $\Gamma$ takes $\tilde O(m^{4/3})$ time
    + Note that $\Gamma$ is on $G$, not only vertices in $Q$
+ Since we will reinitialize after $m^{2/3}$ updates, so the amortized cost for every update is $\tilde O(m^{4/3}/m^{2/3})=\tilde O(m^{2/3})$
#### Update
+ Initially all active vertices are in $P$, and $Q$ is empty
+ $P$: $Delete$ only
+ When $Update$ ($Insert$/$Delete$) a vertex $v$ from $Q$
    + Update $G^*$: check for every vertex in $G^*$ whether it is adjacent to $v$, update those edges
    + Time: $\tilde O(m^{2/3})$
    ![](https://i.imgur.com/QUMGOEI.png)
+ When $Delete$ a vertex of a low component in $P$ 
    + Recompute the edges in $\Gamma$ generated by it
    + Update those edges in $G^*$
    ![](https://i.imgur.com/ouR5fQT.png)
    + Since the number of edges associate with that low component is at most $m^{1/3}$, we may need to update $O((m^{1/3})^2)=O(m^{2/3})$ edges in $G^*$, thus will take $\tilde O(m^{2/3})$ time
+ When $Delete$ a vertex of a **high** component in $P$
    + The new components it generates may be high or low
    + Rank the new components by the sum of degrees: $R_1,R_2,...,R_k$ (from high to low)
    + Consider the new high components
        + Cost of deleting edges in $P$: In total of one phase is $\tilde O(m)$
        + Time needed to update $G^*$: $O(deg(R_2)+deg(R_3)+...+deg(R_k))$ Since $deg(R_2),deg(R_3),...,deg(R_k)$ are at most half of $deg(r)$, where $r$ is origin component, every edge can be moved at most $\log n$ times, so the total time per phase is still $\tilde O(m)$
            ![](https://i.imgur.com/E4kOKrh.png) 
            ![](https://i.imgur.com/b1hsyeJ.png)
        + So it is $\tilde O(m/m^{2/3}) = \tilde O(m^{1/3})$ per updates
    + For the new low components
        + Compute the edges of $\Gamma$ generated by them
        + Since an edge can be in a new low component from a high component only once, so the total cost of time is $\tilde O((m^{2/3})^2)=\tilde O(m^{4/3})$, absorbed by the preprocess cost
### Conclusion
+ Preprocessing Time: $\tilde O(m^{4/3})$
+ Amortized Update Time: $\tilde O(m^{2/3})$
+ Query Time: $\tilde O(m^{1/3})$
+ Space: $\tilde O(m^{4/3})$ (The space needed to store $\Gamma$, we have improved it to $O(m)$)
## Summary
| |Edge Updates| Vertex Updates (Subgraph)|
|---|---|---|
|Amortized|$O(\log^2n)$[*Holm, Lichtenberg & Thorup ’1998*]|$\tilde O(m^{2/3})$, with query time $\tilde O(m^{1/3})$ [*Chan, Pâtraşcu & Roditty ‘2008*]|
|Worst-Case|$O(n^{1/2})$ [$O(m^{1/2})$ by *Frederickson ’1985*] [Improved by *Eppstein, Galil, Italiano, Nissenzweig ‘1992*]|$\tilde O(m^{4/5})$, with query time $\tilde O(m^{1/5})$ [*Duan 2010*]|
|Worst-Case Randomized|$O(\log^5n)$ [*Kapron, King & Mountjoy ’13*]|$\tilde O(m^{3/4})$, with query time $\tilde O(m^{1/4})$ [*Duan & Zhang 2017*]|
+ **Open Problem**: improve amortized vertex update time
+ [*Henzinger, Krinninger, Nanongkai, Saranurak‘15*] shows worst-case randomized vertex update it’s OMv-hard to get a polynomial preprocessing structure with $o(m)$ product of update time and query time



