patternMinor
Split-Find: maintaining dynamic graph connectivity information, under edge deletion
Viewed 0 times
findgraphedgesplitunderdeletiondynamicmaintainingconnectivityinformation
Problem
Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph?
Let $G$ be an undirected graph. I have two operations I'd like to be able to perform:
-
Delete$(u,v)$: delete the edge $(u,v)$ from the graph.
-
SameComponent$(u,v)$: returns true or false according to whether $u,v$ are in the same connected component
Is there a data structure that allows me to perform both operations relatively efficiently?
The naive data structure is simply to store the graph in adjacency list representation, and answer SameComponent$(u,v)$ queries by doing a depth-first search from $u$ to see if $v$ is reachable. However, that makes the SameComponent operation take linear time, and it feels like it is re-doing a lot of work, so maybe there is a more efficient algorithm. Is there a data structure where both operations can be done in sub-linear running time?
One way to think about it is that I am basically asking for the dual of the Union-Find data structure. The Union-Find data structure offers two operations:
-
Union$(u,v)$: add an edge $(u,v)$ to the graph.
-
Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).
You could think of this question as asking for a Split-Find data structure, which should support two operations:
-
Split$(u,v)$: delete the edge $(u,v)$ from the graph.
-
Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).
As we know, there is an efficient Union-Find data structure. The apparent symmetry between Union-Find and Split-Find makes me wonder whether there is also an efficient Split-Find data structure, too.
Of course, if we had an efficient Split-Find data structure, we could answer the original problem: Delete$(u,v)$ would be
Let $G$ be an undirected graph. I have two operations I'd like to be able to perform:
-
Delete$(u,v)$: delete the edge $(u,v)$ from the graph.
-
SameComponent$(u,v)$: returns true or false according to whether $u,v$ are in the same connected component
Is there a data structure that allows me to perform both operations relatively efficiently?
The naive data structure is simply to store the graph in adjacency list representation, and answer SameComponent$(u,v)$ queries by doing a depth-first search from $u$ to see if $v$ is reachable. However, that makes the SameComponent operation take linear time, and it feels like it is re-doing a lot of work, so maybe there is a more efficient algorithm. Is there a data structure where both operations can be done in sub-linear running time?
One way to think about it is that I am basically asking for the dual of the Union-Find data structure. The Union-Find data structure offers two operations:
-
Union$(u,v)$: add an edge $(u,v)$ to the graph.
-
Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).
You could think of this question as asking for a Split-Find data structure, which should support two operations:
-
Split$(u,v)$: delete the edge $(u,v)$ from the graph.
-
Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).
As we know, there is an efficient Union-Find data structure. The apparent symmetry between Union-Find and Split-Find makes me wonder whether there is also an efficient Split-Find data structure, too.
Of course, if we had an efficient Split-Find data structure, we could answer the original problem: Delete$(u,v)$ would be
Solution
It sounds like you're looking for "decremental connectivity". The fastest result I could find was Wulff-Nilson's "Faster deterministic fully-dynamic graph connectivity", which "supports updates (edge insertions/deletions) in $O(\log^2 n/ \log \log n)$ amortized time and connectivity queries in $O(\log n/ \log \log n)$ worst-case time, where $n$ is the number of vertices of the graph."
Context
StackExchange Computer Science Q#32077, answer score: 5
Revisions (0)
No revisions yet.