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

<ul>
<li>Connected($u$,$v$) : Check whether vertex $u$ is connected to vertex $v$</li>
<li>Delete($e$): Remove an edge $e$</li>
</ul>

<p>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].</p>

<p>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)$. </p>

<p>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].</p>

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

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

CC BY-SA 3.0
2014-10-31T04:50:02.337Z
2015-03-03T10:25:39.707Z
2015-03-03T10:25:39.707Z
S. Pek
<p>I am trying to write a data structure that given a general tree (or forest) will support the following operations:</p>

<ol>
<li>Edge deletion</li>
<li>Connected(u,v) queries</li>
</ol>

<p>This problem is addressed in section two of the following ACM journal article: "<a href="http://dl.acm.org/citation.cfm?id=322235" rel="nofollow">An On-Line Edge-Deletion Problem</a>". The idea given claims to be able to carry out <em>q</em> edge deletions in <code>O(q + |V|log|V|)</code> 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. </p>

CC BY-SA 3.0
2014-10-30T19:14:04.990Z
I just realized that I can run the parallel traversals before deleting the edge, and delete it during the traversal once its discovered. I guess that answers the question.
Yechiel Labunskiy
CC BY-SA 3.0
2014-10-30T21:34:28.797Z
In addition to the adjacency list, each node points to its parent (or null, if no parent exists). To check whether $u$ and $v$ are adjacent check whether $u = parent(v) \vee v = parent(u)$.
daniello
<graph-algorithms><tree>
Graph (Forest) representation that supports edge deletion and efficient traversal
Yechiel Labunskiy
# Graph (Forest) representation that supports edge deletion and efficient traversal

(Asked by: username_0 on 2014-10-30)

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](http://dl.acm.org/citation.cfm?id=322235)". 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.

**Tags:** graph-algorithms, tree

> **Comments:**
> **username_0**: I just realized that I can run the parallel traversals before deleting the edge, and delete it during the traversal once its discovered. I guess that answers the question.  
> **username_1**: In addition to the adjacency list, each node points to its parent (or null, if no parent exists). To check whether $u$ and $v$ are adjacent check whether $u = parent(v) \vee v = parent(u)$.  

---

## 1 answers

### Answer by username_2 on 2014-10-31. Score: 3 | Accepted answer

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


---

