Reverse-delete algorithm

The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph. It first appeared in Kruskal (1956), but it should not be confused with Kruskal's algorithm which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.

This algorithm is a greedy algorithm, choosing the best choice given any situation. It is the reverse of Kruskal's algorithm, which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:

Start with graph G, which contains a list of edges E.
Go through E in decreasing order of edge weights.
For each edge, check if deleting the edge will further disconnect the graph.
Perform any deletion that does not lead to additional disconnection.

Pseudocode

 1  function ReverseDelete(edges[] E)
 2    sort E in decreasing order
 3    Define an index i ← 0
 4    while i < size(E)
 5       Define edge ← E[i]
 6	   delete E[i]
 7	   if edge.v1 is not connected to edge.v2
 8             E[i] ← edge
 9   	   i ← i + 1
 10   return edges[] E

In the above the graph is the set of edges E with each edge containing a weight and connected vertices v1 and v2.

Example

In the following example green edges are being evaluated by the algorithm and red edges have been deleted.

	This is our original graph. The numbers near the edges indicate their edge weight.
	The algorithm will start with the maximum weighted edge, which in this case is DE with an edge weight of 15. Since deleting edge DE does not further disconnect the graph it is deleted.
	The next largest edge is FG so the algorithm will check if deleting this edge will further disconnect the graph. Since deleting the edge will not further disconnect the graph, the edge is then deleted.
	The next largest edge is edge BD so the algorithm will check this edge and delete the edge.
	The next edge to check is edge EG, which will not be deleted since it would disconnect node G from the graph. Therefore, the next edge to delete is edge BC.
	The next largest edge is edge EF so the algorithm will check this edge and delete the edge.
	The algorithm will then search the remaining edges and will not find another edge to delete; therefore this is the final graph returned by the algorithm.

Running time

The algorithm can be shown to run in O(E log V (log log V)³) time, where E is the number of edges and V is the number of vertices. This bound is achieved as follows:

sorting the edges by weight using a comparison sort in O(E log E) time
E iterations of loop
deleting in O(1) time
connectivity checked in O(logV (log log V)³) time (Thorup 2000).

Equally, the running time can be considered O(E log E (log log E)³) because the largest E can be is V². Remember that logV² = 2 * logV, so 2 is a multiplicative constant that will be ignored in big-O notation.

Proof of correctness

The proof consists of two parts. First, it is proved that the edges that remain after the algorithm is applied form a spanning tree. Second, it is proved that the spanning tree is of minimal weight.

Spanning tree

The remaining sub-graph (g) produced by the algorithm is not disconnected since the algorithm checks for that in line 7. the resualt sub-graph cannot contain a cycle since if it does then when moving along the edges we would encounter the max edge in the cycle and we would delete that edge.thus g must be a spanning tree of the main graph G.

Minimality

We show that the following proposition P is true by induction: If F is the set of edges remained after the while loop, then there is some minimum spanning tree that (it's edges) are a subset of F.

References

Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, New York: Pearson Education, Inc..
Kruskal, Joseph B. (1956), "On the shortest spanning subtree of a graph and the traveling salesman problem", Proceedings of the American Mathematical Society, 7 (1): 48–50, JSTOR 2033241.
Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, doi:10.1145/335305.335345.