Fully Dynamic Higher Connectivity

Keywords and Synonyms

Fully dynamic edge connectivity; Fully dynamic vertex connectivity        

Problem Definition

The problem is concerned with efficiently maintaining information about edge and vertex connectivity in a dynamically changing graph. Before defining formally the problems, a few preliminary definitions follow.

Given an undirected graph ${ G=(V,E) }$, and an integer ${ k\geq 2 }$, a pair of vertices ${ \langle u,v\rangle }$ is said to be k‑edge‐connected if the removal of any ${ (k-1) }$ edges in G leaves u and v connected. It is not difficult to see that this is an equivalence relationship: the vertices of a graph G are partitioned by this relationship into equivalence classes called k‑edge‐connected components. G is said to be k‑edge‐connected if the removal of any ${ (k-1) }$ edges leaves G connected. As a result of these definitions, G is k‑edge‐connected if and only if any two vertices of G are k‑edge‐connected. An edge set ${ E^{\prime}\subseteq E }$ is an edge-cut for vertices x and y if the removal of all the edges in ${ E^{\prime} }$ disconnects G into two graphs, one containing x and the other containing y. An edge set ${ E^{\prime}\subseteq E }$ is an edge-cut for G if the removal of all the edges in ${ E^{\prime} }$ disconnects G into two graphs. An edge-cut ${ E^{\prime} }$ for G (for x and y, respectively) is minimal if removing any edge from ${ E^{\prime} }$ reconnects G (for x and y, respectively). The cardinality of an edge-cut ${ E^{\prime} }$, denoted by ${ |E^{\prime}| }$, is given by the number of edges in ${ E^{\prime} }$. An edge-cut ${ E^{\prime} }$ for G (for x and y, respectively) is said to be a minimum cardinality edge-cut or in short a connectivity edge-cut if there is no other edge-cut ${ E^{\prime\prime} }$ for G (for x and y respectively) such that ${ |E^{\prime\prime}|<|E^{\prime}| }$. Connectivity edge-cuts are of course minimal edge-cuts. Note that G is k‑edge‐connected if and only if a connectivity edge-cut for G contains at least k edges, and vertices x and y are k‑edge‐connected if and only if a connectivity edge-cut for x and y contains at least k edges. A connectivity edge-cut of cardinality 1 is called a bridge.

The following theorem due to Ford and Fulkerson, and Elias, Feinstein and Shannon (see [7]) gives another characterization of k‑edge connectivity.

Theorem 1 (Ford and Fulkerson, Elias, Feinstein and Shannon)

Given a graph G and two vertices x and y in G, x and y are k‑edge‐connected if and only if there are at least k edge-disjoint paths between x and y.

In a similar fashion, a vertex set ${ V^{\prime}\subseteq V-\{x,y\} }$ is said to be a vertex-cut for vertices x and y if the removal of all the vertices in ${ V^{\prime} }$ disconnects x and y. ${ V^{\prime}\subset V }$ is a vertex-cut for vertices G if the removal of all the vertices in ${ V^{\prime} }$ disconnects G.

The cardinality of a vertex-cut ${ V^{\prime} }$, denoted by ${ |V^{\prime}| }$, is given by the number of vertices in ${ V^{\prime} }$. A vertex-cut ${ V^{\prime} }$ for x and y is said to be a minimum cardinality vertex-cut or in short a connectivity vertex-cut if there is no other vertex-cut ${ V^{\prime\prime} }$ for x and y such that ${ |V^{\prime\prime}|<|V^{\prime}| }$. Then x and y are k‑vertex‐connected if and only if a connectivity vertex-cut for x and y contains at least k vertices. A graph G is said to be k‑vertex‐connected if all its pairs of vertices are k‑vertex‐connected. A connectivity vertex-cut of cardinality 1 is called an articulation point, while a connectivity vertex-cut of cardinality 2 is called a separation pair. Note that for vertex connectivity it is no longer true that the removal of a connectivity vertex-cut splits G into two sets of vertices.

The following theorem due to Menger (see [7]) gives another characterization of k‑vertex connectivity.

Theorem (Menger) 2

Given a graph G and two vertices x and y in G, x and y are k‑vertex‐connected if and only if there are at least k vertex‐disjoint paths between x and y.

A dynamic graph algorithm maintains a given property ${ {\cal P} }$ on a graph subject to dynamic changes, such as edge insertions, edge deletions and edge weight updates. A dynamic graph algorithm should process queries on property ${ {\cal P} }$ quickly, and perform update operations faster than recomputing from scratch, as carried out by the fastest static algorithm. An algorithm is fully dynamic if it can handle both edge insertions and edge deletions. A partially dynamic algorithm can handle either edge insertions or edge deletions, but not both: it is incremental if it supports insertions only, and decremental if it supports deletions only.

In the fully dynamic k‑edge connectivity problem one wishes to maintain an undirected graph ${ G = (V, E) }$ under an intermixed sequence of the following operations:

• k‑EdgeConnected(u, v): Return true if vertices u and v are in the same k‑edge‐connected component. Return false otherwise.

• Insert(x, y): Insert a new edge between the two vertices x and y.

• Delete(x, y): Delete the edge between the two vertices x and y.

In the fully dynamic k‑vertex connectivity problem one wishes to maintain an undirected graph ${ G = (V, E) }$ under an intermixed sequence of the following operations:

• k‑VertexConnected(u, v): Return true if vertices u and v are k‑vertex‐connected. Return false otherwise.

• Insert(x, y): Insert a new edge between the two vertices x and y.

• Delete(x, y): Delete the edge between the two vertices x and y.

Key Results

To the best knowledge of the author, the most efficient fully dynamic algorithms for k‑edge and k‑vertex connectivity were proposed in [3,12]. Their running times are characterized by the following theorems.

Theorem 3

The fully dynamic k‑edge connectivity problem can be solved in:

• 1. ${ O(\log ^{4} n) }$ time per update and ${ O(\log^3 n) }$ time per query, for ${ k=2 }$

• 2. ${ O(n^{2/3}) }$ time per update and query, for ${ k=3 }$

• 3. ${ O(n\alpha (n)) }$ time per update and query, for ${ k=4 }$

• 4. ${ O(n\log n) }$ time per update and query, for ${ k\geq 5\:. }$

Theorem 4

The fully dynamic k‑vertex connectivity problem can be solved in:

• 1. ${ O(\log ^{4} n) }$ time per update and ${ O(\log^3 n) }$ time per query, for ${ k=2 }$

• 2. O(n) time per update and query, for ${ k=3 }$

• 3. ${ O(n\alpha (n)) }$ time per update and query, for ${ k=4\:. }$

Applications

Vertex and edge connectivity problems arise often in issues related to network reliability and survivability. In computer networks, the vertex connectivity of the underlying graph is related to the smallest number of nodes that might fail before disconnecting the whole network. Similarly, the edge connectivity is related to the smallest number of links that might fail before disconnecting the entire network. Analogously, if two nodes are k‑vertex‐connected then they can remain connected even after the failure of up to ${ (k-1) }$ other nodes, and if they are k‑edge‐connected then they can survive the failure of up to ${ (k-1) }$ links. It is important to investigate the dynamic versions of those problems in contexts where the networks are dynamically evolving, say, when links may go up and down because of failures and repairs.

Open Problems

The work of Eppstein et al. [3] and Holm et al. [12] raises some intriguing questions. First, while efficient dynamic algorithms for k‑edge connectivity are known for general k, no efficient fully dynamic k‑vertex connectivity is known for ${ k\geq 5 }$. To the best of the author's knowledge, in this case even no static algorithm is known. Second, fully dynamic 2-edge and 2‑vertex connectivity can be solved in polylogarithmic time per update, while the best known update bounds for higher edge and vertex connectivity are polynomial: Can this gap be reduced, i. e., can one design polylogarithnmic algorithms for fully dynamic 3-edge and 3‑vertex connectivity?

Cross References

Dynamic Trees

Fully Dynamic All Pairs Shortest Paths

Fully Dynamic Connectivity

Fully Dynamic Higher Connectivity for Planar Graphs

Fully Dynamic Minimum Spanning Trees

Fully Dynamic Planarity Testing

Fully Dynamic Transitive Closure