Dynamic Trees:Topology Trees

Topology Trees

Topology trees have been introduced by Frederickson [6] in order to maintain information about trees subject to insertions and deletions of edges and answer efficiently, e.g., tree membership queries. Similarly to the linking and cutting trees of Sleator and Tarjan [15] that we have discussed in Section 35.2, topology trees follow the idea of partitioning a tree into a set of vertex-disjoint paths. However, they are very different in how this partition is chosen, and in the data structures used to represent the paths inside the partition. Indeed, Sleator and Tarjan [15] use a simple partition of the trees based upon a careful choice of sophisticated data structures to represent paths. On the contrary, Frederickson [6] uses a more sophisticated partition that is based upon the topology of the tree; this implies more complicated algorithms but simpler data structures for representing paths.

The basic idea is to partition the tree into a suitable collection of subtrees, called clusters,

and to implement updates such that only a small number of such clusters is involved. The decomposition defined by the clusters is applied recursively to get faster update and query times.

In order to illustrate how such a recursive decomposition is computed, we assume that T has maximum vertex degree 3: this is without loss of generality, since a standard transformation can be applied if this is not the case [9]. Namely, each vertex v of degree d > 3 is replaced by new vertices v0,..., vd−1; for each neighbor ui of vertex v, 0 ≤ i ≤ d − 1, edge (v, ui) is replaced by (vi, ui), and a new edge (vi, vi+1) is created if i < d − 1.

Given a tree T of maximum degree 3, a cluster is any connected subgraph of T . The cardinality and the external degree of a cluster are the number of its vertices and the number of tree edges incident to it, respectively. We now define a partition of the vertices of T such that the resulting clusters possess certain useful properties. Let z be a positive integer.

DEFINITION 35.1 A restricted partition of order z w.r.t. T is a partition of the vertex set V into clusters of degree at most 3 such that:

(1) Each cluster of external degree 3 has cardinality 1.

(2) Each cluster of external degree < 3 has cardinality at most z.

(3) No two adjacent clusters can be combined and still satisfy the above.

A restricted partition of order 2 of a tree T is shown in Figure 35.4. There can be several restricted partitions for a given tree T , based upon different choices of the vertices to be unioned. For instance, vertex 8 in Figure 35.4 could be unioned with 7, instead of 11, and the partition would still be valid. It can be proved that a restricted partition of order z has Θ(n/z) clusters [6, 7].

We now show that the partition defined above can be applied recursively for Θ(log n) levels. Such a recursive application yields a restricted multilevel partition [6, 7], from which the topology tree can be finally obtained.

DEFINITION 35.2 A topology tree is a hierarchical representation of a tree T such that each level of the topology tree partitions the vertices of T into clusters. Clusters at level 0

contain one vertex each. Clusters at level £ ≥ 1 form a restricted partition of order 2 of the vertices of the tree T I obtained by shrinking each cluster at level £ − 1 into a single vertex.

As shown in Figure 35.5, level l of the restricted multilevel partition is obtained by computing a restricted partition of order 2 with respect to the tree resulting from viewing each cluster at level l − 1 as a single vertex. Figure 35.5 also shows the topology tree corresponding to the restricted multilevel partition. Call any cluster of level l − 1 matched if it is unioned with another cluster to give a cluster of level l: unmatched clusters have a unique child in the topology tree. It can be proved that, for any level l > 0 of a restricted multilevel partition, the number of matched clusters at level l − 1 is at least 1/3 of the total number of vertex clusters at level l − 1. Since each pair of matched clusters is replaced by their union at level l, the number of clusters at level l is at most 5/6 the number of clusters at level l − 1. The number of levels of the topology tree is therefore Θ(log n).

Construction

It is sufficient to show how to compute a restricted partition: the levels of the topology tree can be then built in a bottom up fashion by repeatedly applying the clustering algorithm as suggested by Definition 35.2. Because of property (3) in Definition 35.1, it is natural to compute a restricted partition according to a locally greedy heuristic, which does not al- ways obtain the minimum number of clusters, but has the advantage of requiring only local adjustments during updates. The tree is first rooted at any vertex of degree 1 and the proce- dure cluster is called with the root as argument. At a generic step, procedure cluster(v) works as follows. It initializes the cluster C(v) containing vertex v as C(v) = {v}. Then, for each child w of v, it recursively calls cluster(w), that computes C(w): if C(w) can be unioned with C(v) without violating the size and degree bounds in Definition 35.1, C(v) is updated as C(v) ∪ C(w), otherwise C(w) is output as a cluster. As an example, the restricted partition shown in Figure 35.4 is obtained by running procedure cluster on the tree rooted at vertex 7.

Updates

We first describe how to update the clusters of a restricted partition when an edge e is inserted in or deleted from the dynamic tree T : this operation is the crux of the update of the entire topology tree.

Update of a restricted partition. We start from edge deletion. First, removing an edge e splits T into two trees, say T1 and T2, which inherit all of the clusters of T , possibly with the following exceptions.

1. Edge e is entirely contained in a cluster: this cluster is no longer connected and therefore must be split. After the split, we must check whether each of the two resulting clusters is adjacent to a cluster of tree degree at most 2, and if these two adjacent clusters together have cardinality ≤ 2. If so, we combine these two clusters in order to maintain condition (3).

2. Edge e is between two clusters: in this case no split is needed. However, since the tree degree of the clusters containing the endpoints of e has been decreased, we must check if each cluster should be combined with an adjacent cluster, again because of condition (3).

Similar local manipulations can be applied to restore invariants (1) - (3) in Definition 35.1 in case of edge insertions. We now come to the update of the topology tree.

Update of the topology tree. Each level can be updated upon insertions and deletions of edges in tree T by applying few locally greedy adjustments similar to the ones described above. In particular, a constant number of basic clusters (corresponding to leaves in the topology tree) are examined: the changes in these basic clusters percolate up in the topology tree, possibly causing vertex clusters to be regrouped in different ways. The fact that only a constant amount of work has to be done on O(log n) topology tree nodes implies a logarithmic bound on the update time.

THEOREM 35.3 [6, 7] The update of a topology tree because of an edge insertion or deletion in the dynamic tree T can be supported in O(log n) time, where n is the number of vertices of T .

Applications

In the fully dynamic tree membership problem we would like to maintain a forest of unrooted trees under insertion of edges (which merge two trees into one), deletion of edges (which split one tree into two), and membership queries. Typical queries require to return the name of the tree containing a given vertex, or ask whether two vertices are in a same tree. Most of the solutions presented in the literature root each tree arbitrarily at one of its vertices; by keeping extra information at the root (such as the name of the tree), membership queries are equivalent to finding the tree root a vertex.

The dynamic tree clustering techniques of Frederickson have also found wide application in dynamic graph algorithms. Namely, topology trees have been originally designed in order to solve the fully dynamic minimum spanning tree problem [6], in which we wish to maintain a minimum spanning tree of a dynamic weighted undirected graph upon insertions/deletions of edges and edge cost changes. Let G = (V, E) be the dynamic graph and let S be a designated spanning tree of G. As G is updated, edges in the spanning tree S may change: e.g., if the cost of an edge e is increased in G and e is in the spanning tree, we need to check for the existence of a replacement edge eI of smaller cost, and swap eI with e in S. The clustering approach proposed in [6, 7] consists of partitioning the vertex set V into subtrees connected in S, so that each subtree is only adjacent to a few other subtrees. A topology tree is used for representing this recursive partition of the spanning tree S. A generalization of topology trees, called 2-dimensional topology trees, is also formed from pairs of nodes in the topology tree in order to maintain information about the edges in E \ S [6]. Fully dynamic algorithms based only on a single level of clustering obtain typically time bounds of the order of O(m2/3 ) (see for instance [8, 14]), where m is the number of edges of the graph. When the partition is applied recursively, better O(m1/2) time bounds can be achieved by using 2-dimensional topology trees:

we refer the interested reader to [6, 7] for details. As

we will see in Section 36.5.2, Frederickson’s algorithm is not optimal:

the fully dynamic minimum spanning tree problem has been later solved in polylogarithmic time [11].

With the same technique, an O(m1/2) time bound can be obtained also for fully dynamic connectivity and 2-edge connectivity [6, 7]. For instance, [7] shows that edges and vertices can be inserted to or deleted from an undirected graph in O(m1/2) time, and a query as to whether two vertices are in the same 2-edge-connected component can be answered in O(log n) time, n being the number of vertices. This result is based on the use of ambivalent data structures [7], a refinement of the clustering technique in which edges can belong to multiple groups, only one of which is actually selected depending on the topology of the given spanning tree.