Graph (Forest) representation that supports edge deletion and efficient traversal

Question

I am trying to write a data structure that given a general tree (or forest) will support the following operations:

1. Edge deletion
2. Connected(u,v) queries

This problem is addressed in section two of the following ACM journal article: "An On-Line Edge-Deletion Problem". The idea given claims to be able to carry out q edge deletions in O(q + |V|log|V|) time, while allowing constant time Connected(u,v) queries. The idea being: to maintain a table mapping each vertex to a connected component. Upon each deletion, each of the new trees is scanned in parallel. Which ever tree is finished being scanned first - becomes a new component. Now my question is, which graph representation can I use to implement their idea? On one hand I need to be able to delete an edge without having to scan an O(|V|) adjacency list, on the other hand, I need to be able to run a traversal (DFS) in O(|E|) = O(|V| (tree) time which can't happen using a matrix.

Answer 1

This problem is known as Decremental Connectivity. In general, decremental connectivity is where you need to support the operations:

• Connected($u$,$v$) : Check whether vertex $u$ is connected to vertex $v$
• Delete($e$): Remove an edge $e$

Given $n$ queries of the first kind and $m$ queries of the second, Even and Shiloach [1] gave an $O(n\log{n} + m)$ algorithm and later, Alstrup et al. gave an $O(n+m)$ algorithm in [2].

There is a simple way to do the former using a data-structure known as the Euler Tour Trees or the approach taken in [1] could also be used. If you wish to implement [1], the tree is stored as a set of connected components. It is then enough to determine which component each vertex belongs to answer the connected-ness query. There is a breadth-first seach used to answer the deletion process. But it is $O(\log{n})$ amortized. This would achieve $O(n\log{n} + m)$.

If the $\log{n}$ factor must be removed, then a leaf-trimming approach would work. You trim all subtrees with size $\geq\log{n}$. Then, you can use the Euler Tour Trees (or the approach in [1]) to perform queries in the untrimmed portion. Some cases could need to be seperately handled. This is the approach given in [2].

[1] S. Even and Y. Shiloah. An on-line edge-deletion problem. Journal of the Assoiation for Computing Mahinery, 28:1-4, 1981.

[2] Stephen Alstrup and Jens Peter Secher and Maz Spork. Optimal On-line Decremental Connectivity in Trees, IPL, 65:64-8, 1997