# 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
### 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$
+ $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
+ **However, enumerating edges will be time consuming**
### *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}}$
+ 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}}$
+ 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$)
+ 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))$
:::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$
+ 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$
+ $f$ connect $T(u)$ and $T(v)$, stop the search, and add $f$ to $F_0$, $F_1$,...,$F_i$
+ 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)
+ Deleting a tree edge
+ Call $Reconnect(e, \ell(e))$
+ Check for an edge whether it can reconnect them
+ Remove it to higher level
+ Call reconnect in lower level
#### 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
+ 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})$
#### 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$
+ 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}$

+ 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^*$
### 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})$
+ When $Delete$ a vertex of a low component in $P$
+ Recompute the edges in $\Gamma$ generated by it
+ Update those edges in $G^*$
+ 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)$
+ 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