Finding Optimal Spanning Trees For Damaged Networks

1. History

The history of the minimum spanning trees can be found in many papers. In [1] details of all the classical algorithms related to the minimal spanning tree problem are analayzed. In [2] the asymptotical complexity of the methods used to solve different types of optimum undirected tree problem are discussed. In [3] an insight to the algorithmic technique for solving the minimal spanning tree problem is provided. In [4] various computational methods for MST algorithms are discussed. Non-greedy approaches for MST are found in [5]. In [6] a survey of different computational experiments is given. A nice recent survey is [7].

In this paper, we follow the notation in [8]. Many of the ideas discussed here can be found in the two excellent sources [8] and [9]. Let $G$ be a simple, connected, and rooted graph with a vertex set $V(G)$, an edge set $E(G)$, and a root vertex $v^{\ast }$. We let $|V|$ and $|E|$ denote the number of vertices and edges, respectively, and we let V* denote the set of non-root vertices.

2. Motivation

The motivation to study this came from working on computer networks for the first author. He was developing a network protocol that would recover very quickly if a link or node were to fail. The idea was that a sub-optimal spanning tree might be found quickly and then migrate, one step at a time, to an optimal spanning tree. At every step the network would still have a functional spanning tree. In order for the migration to be possible, the collection of spanning tree for the damaged network had to be connected.

A spanning tree $T$ of $G$ is a subgraph of $G$ containing no cycles and having $|V|–1$ edges. For more on spanning trees see [10]. We will let $T$ denote both the spanning tree itself and its edge set. While $G$ and $T$ are undirected graphs, it is useful to think the edges of $T$ as having an orientation which points in the direction of $v^{\ast }$ along a path in $T$.

For any vertex $v$ in $V(G)$, we let $N(v)=\{w\in V|(v,w)$ is an edge in $E\}$. We say $N(v)$ is the set of nearest neighbors of v. Each edge $e$ in $E(G)$ has an associated positive cost. Any path in $G$ has an associated cost which is equal to the sum of its edge costs. For any vertex $v$ in $V(G)$, there is a shortest path cost, denoted by $c(v)$, which is the minimum path cost over all paths in $G$ between $v$ and $v^{\ast }$. It follows that $c(v^{\ast })$ is zero and that, for any other vertex $v$, $c(v)$ is positive. A shortest path spanning tree $T^{\prime }$ has the property that for any vertex $v$, the cost $c(v)$ is equal to the cost of the (only) path in $T^{\prime }$ between $v$ and $v^{\ast }$. It follows that if $w$ is another vertex on the path in $T^{\prime }$ between $v$ and $v^{\ast }$, then $c(w)<c(v)$. A graph $G$ always has a shortest path spanning tree and in general it is not unique.

3. A Few Observations

For any spanning tree $T$, and for any vertex $v$ in $V^{\ast }$, there is a unique path in $T$, having at least one edge, between $v$ and $v^{\ast }$. It follows that there is a unique vertex $P(v)$, called the parent of $v$, which is a nearest neighbor of $v$ and is closer to $v^{\ast }$ along the same path. The root vertex $v^{\ast }$ has no parent, but it may be the parent of another vertex. The spanning tree $T$ is completely described by its parent function $P_T:V^{\ast }\to V$. Note that an arbitrarily defined parent function may not correspond to a valid spanning tree (e.g. arbitrary $P(v)$ might not be a nearest neighbor. For future reference, we make the following observations here:

1. Let $T$ be a spanning tree of $G$ with parent function $P$.

2. Let $T^{\prime }$ be a shortest path spanning tree of $G$ with parent function $P^{\prime }$. Since path-cost on $T^{\prime }$ is identical to path-cost on $G$, then it follows that $c(P^{\prime }(v))<c(v)$ for any $v$ in $V^{\ast }$.

3. Let the set $V$ of all vertices be sorted in order of increasing path cost. Thus, we have: $V=\{v_k|0\le k\le |V|-1$ and if $i<j$ then $c(v_i)\le c(v_j)\}$. The lowest cost vertex is $v_0=v^{\ast }$ and $c(v_0)=0$ .

4. Let $A(k)=\{v_j|1\le j<k\}$ and $B(k)=\{v_j|k\le j<|V|\}$ for $1\le k\le |V|$. Now $A(1)=\mathrm{\varnothing },A(|V|)=V^{\ast },B(1)=V^{\ast },B(|V|)=\mathrm{\varnothing }$, and $A(k)\cap B(k)=\mathrm{\varnothing }$ .5cm for any $k$.

5. Let $\{P_k^{″}|1\le k\le |V|\}$ be a sequence of parent functions such that $P_k^{″}=P^{\prime }$ on $A(k)$ and $P_k^{″}=P$ on $B(k)$.

6. Let $A^{\ast }(k)=\{v^{\ast }\}\cup A(k)$

We want to show that any parent function $P$ corresponding to spanning tree $T$ can be modified, one step at a time, to reach parent function $P^{\prime }$ corresponding to shortest path spanning tree $T^{\prime }$. The modified parent functions are denoted by $P^{″}$ and it is important to show that each of them corresponds to a spanning tree $T^{″}$ (and doesn’t generate a loop such as the example above). The machinery of the proof is to write the vertices of the graph in order of path cost; that means that $v_0$ is the root (cost=0), $v_1$ is the next low-cost vertex, etc until we come to $v_{|V^{\ast }|}$ which is the most path-costly vertex.

We define $A(k)$ and $B(k)$ wherein all the vertices in $A(k)$ are less path-costly than all the vertices in $B(k)$. As the value of $k$ goes from 1 to $|V|$, we create the sequence of parent functions $P_k^{″}$ such that the sequence starts with function $P$ and ends with function $P^{\prime }$. We argue that each $P_k^{″}$ corresponds to a spanning tree $T_k^{″}$. In this sequence of modified parent functions, $P_k^{″}$ is followed by $P_{k+1}^{″}$. We show that these functions differ only at vertex $v_k$ which means they are distance apart and hence adjacent and connected. The corresponding spanning trees are $T_k^{″}$ and $T_{k+1}^{″}$ , respectively.

The last parent function in the migration sequence is $P_{|V|}^{″}$ which equals $P^{\prime }$, the desired goal. The value $k$ acts like a slider from 1 to $|V|$: $A(k)$ and $B(k)$ form a partition of the vertices. At $k=1$, $A(1)$ is empty and $B(1)$ is the entire list of vertices and $P_1^{″}$ is $P$. At $k=|V|$, $A(|V|)$ is the entire list of vertices and $B(|V|)$ is empty and $P_{|V|}^{″}$ is $P^{\prime }$, the goal.

4. Main result

Now imagine that spanning trees are abstracted as vertices themselves in a graph $H$ of the spanning trees of $G$. Then we could say that two spanning trees $T$ and $T^{\prime }$ are adjacent if and only if their parent functions $P$ and $P^{\prime }$ differ at exactly one vertex. We would then say that $T$ and $T^{\prime }$ are distance one apart. Notice that from (5), distance $(P_i^{″},P_j^{″})\le |i-j|$. Now we ask whether $H$ is also connected or not.

If we now consider $H^{\prime }$, the subgraph of $H$ containing only shortest path spanning trees of $G$, we can have the following immediate consequence:

As a future work, we pose the following question: Can arbitrary spanning trees of $G$ be path connected without using shortest path spanning tree, i.e., is the graph $H^{\ast }=H-H^{\prime }$ connected?