Upper Bound on Local Search MST


Consider a connected weighted graph $ G=(V,E)$ . The local search algorithm is used to find the Minimum Spanning Tree, only swapping one edge for another at a time. At each step of the local search algorithm, select the best improving swapping of edges: $ \{e, f\}$ , where $ w_f – w_e$ is maximized.

Here is how the algorithm works:

Define a spanning tree $ T$ in $ G$ . Let $ e$ be an edge in $ G \setminus T$ , and define $ C$ as the cycle created when $ e$ is added to $ T$ . If $ w_e < w_f$ , where $ f$ is the edge in $ C \setminus \{e\}$ of largest weight, then $ \{e, f\}$ is defined as an improving swap and we set $ T := (T \setminus f) ∪ e$ . We repeat this until there are no more improving swaps.

There exists a finite number of spanning trees in a graph $ G$ . So, when using the best improving swap local search algorithm, there must be an eventual termination of the algorithm in a finite number of steps since the weight of the spanning tree falls in each step.

What I need is an upper bound on the max number of steps the best improving swap local search algorithm will take. Assume every edge weight in the $ G$ is distinct.

I’m really stuck and I’m not sure how to even start this problem, any help would be appreciated.