Maximally distant spanning trees of a graph

Question

I am trying hard to understand the algorithm for finding the maximally distant spanning trees of a graph. I tried to read some paper but could not understand properly as became very deep. Can someone please explain it in a lucid manner with one example? Example can make it very clear.

These are the papers which I am referring to

Maximally Distant Trees and Principal Partition of a Linear Graph ’ GENYA KISHI, MEMBER, IEEE, AND YOJI KAJITANI

On Maximally Distant Spanning Trees of a Graph T. Kameda, Waterloo

Answer 1

Here's an explanation of the algorithm in the second paper.

The algorithm is based on an algorithmic test for two or more trees being maximally distant. (I'll do an example for two trees, but it doesn't really get any more complicated with three or more.) So first, here's the test.

Let $\{T_1, T_2, \dots, T_k\}$ be a set of spanning trees in our graph $G$; let $e$ be an edge of $G$ not in any of the $T_i$. Below is an example for $k=2$; I'll take $G$ to be the complete graph on $5$ vertices.

We define $C_i(\{e\})$ to be the unique cycle spanned by $e$ and the edges of $T_i$. We define $K(\{e\}) := \bigcup_{i=1}^k C_i(\{e\})$ to be the union of all these cycles. Here's how this looks for the example above (the dashed edges are the edges of $T_i$ forming a cycle together with $e$).

We can generalize this: for a set $S$, we can let $C_i(S)$ to be the union of $C_i(\{e\})$ over all $e \in S$ that are not edges of $T_i$. As before, we define $K(S) := \bigcup_{i=1}^k C_i(S)$. This lets us iterate the procedure, and compute $K(K(\{e\}))$.

Repeating this, the sequence $\{e\}, K(\{e\}, K(K(\{e\})), \dots$ eventually stabilizes, and we define the end result to be $K^*(\{e\})$. (In this example, $K^*(\{e\})$ is actually the same as the graph $K(K(\{e\}))$ shown in the previous diagram.)

The test for being maximally distant is now the following:

Trees $T_1, T_2, \dots, T_k$ are maximally distant if and only if, for every choice of the starting edge $e$ (that's not in any of the trees), $K^*(\{e\})$ does not contain any edges repeated in more than one tree $T_i$.

The sufficiency of this condition takes some work to prove, but if you're willing to trust that the algorithm works, we don't need it. The condition is necessary because of the following observation: if we get a common edge in $K^*(\{e\})$, we can use it to improve $T_1, T_2, \dots, T_k$ to make them more distant: covering all the edges they used to cover, as well as the starting edge $e$.

Here's how. We build a sequence of edges starting with $e$ and ending with the common edge $e'$ explaining how we ended up with $e' \in K^*(\{e\})$. In this case, one possible sequence is:

• The edge $e = e_1$ made us add $e_2 \in C_2(\{e_1\})$ to $K^*$.
• The edge $e_2$ made us add $e_3 \in C_1(\{e_2\})$ to $K^*$.
• The edge $e_3$ was the common edge $e'$.

(Edges $e_1, e_2, e_3$ are shown below.)

If that's the case, every time the edge $e_r$ made us add $e_{r+1} \in C_i(\{e_r\})$ to $K^*$, we can update the tree $T_i$ by removing $e_{r+1}$ from it, and adding $e_r$. Doing this keeps $T_i$ a spanning tree, the edge $e = e_1$ is added to some spanning tree, and none of the edges $e_2, e_3, \dots$ are lost, so the union of the edges in the trees gains an extra edge, as shown above.

---

The algorithm for constructing a set of maximally distant trees is basically by repeating the procedure above. Start with an edge $e$ not in any of the trees and apply the test; if the test fails, you'll be able to adjust the trees to also include $e$ in their union. Repeat for all other edges $e$ not in any of the trees.

(As an shortcut, note that once an edge $f$ has appeared in $K^*(\{e\})$ for some $e$, we don't have to run the test starting with $f$, because we'll just get $K^*(\{e\})$ or a subset of it again.)

Once you try this for all the non-tree edges, you know that the test has passed for every edge that's still not in the union of your spanning trees, and therefore the spanning trees are maximally distant.