How to find two disjoint spanning trees of an undirected graph

Question

Is there any applicable approach to find two disjoint spanning trees of an undirected graph or to check if a certain graph has two disjoint spanning trees

Answer 1

According to A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees, this can be solved in O(k²n²) where k is the number of disjoint spanning trees, and n is the number of vertices.

Unfortunately, all but the first page of the article is behind a paywall.

Answer 2

Not sure it helps much in the applicable side but Tutte [1961a] and Nash-Williams [1961] independently characterized graphs having k pairwise edge-disjoint spanning trees:

A graph G has k pairwise edge-disjoint spanning trees iff for every partition of the vertices of G into r sets, there are at least k(r-1) edges of G whose endpoints are in different sets of the partition.

Use k=2 and it may give you a lead for your needs.

Answer 3

Assuming that the desire is to find spanning trees with disjoint edge sets, what about:

1. Given a graph G determining the minimum spanning tree A of G.
2. Defining B = G - A by deleting all edges from G that also lie in A.
3. Checking if B is connected.

The nature of a minimum spanning tree somehow makes me intuitively believe that choosing it as one of the two spanning trees gives you maximum freedom in constructing the other (that hopefully turns out to be edge disjunctive).

What do You guys think?

edit

The above algorithm makes no sense as a spanning tree is a tree and therefore needs to be acyclic. But there is no guarantee that B = G - A is acyclic.

However, this observations (thx@Tormer) led me to another idea:

1. Given a graph G determine the minimum spanning tree A of G.
2. Define B = (V[G], E[G] \ E[A]) where V[G] describes the vertices of G and E[G] describes the edges of G (A respectively).
3. Determine, if B has a spanning tree.

It could very well be that the above algorithm fails although G indeed has two edge disjunctive spanning trees - just no one of them is G's minimum spanning tree. I can't judge this (now), so I'm asking for Your opinion if it's wise to always chose the minimum spanning tree as one of the two.

Answer 4

This could be transformed into a flow-network problem, using the characterization that galbarm mentions:

1. Pick any 2 vertices in the graph and name them S and T.
2. Turn each edge into 2 anti-symmetric edges, each with a capacity of 1.
3. Find a maximum flow from S to T in the network using the Ford–Fulkerson algorithm.

According to the max-flow min-cut theorem, there's a flow of capacity at least 2 if and only if every cut has capacity at least 2. In our case this means there are 2 directed edges in each direction, or 1 undirected edge in the original graph. As galbarm mentions, this means that there are 2 edgewise-disjoint spanning trees.

Complexity-wise, the Ford–Fulkerson algorithm takes O(F*E) time, where F is the maximum flow on the network. Since a flow of 2 is enough in our case, we can stop the algorithm mid-way and get a complexity of O(E).

(Another way is to force a limit of 2 on the flow by adding a vertex S' and an edge of capacity 2 between it and the original S, then finding the flow between S' and T).

There might be an easier way to do this, but I cannot think of one now...

Edited to add: note that in this case O(E) = O(min(E,V^2)), since there's no reason to have more than 2 edges between each pair of vertices.