« One reason I use a Mac | Main | 20 years in the sausage business »

June 10, 2004


David Eppstein

The same proof shows that the mod-k minimum spanning tree is at most k-1 swaps away from the minimum spanning tree.

David Eppstein

Oops, I take that back. It works for k=3 but I'm unsure about larger k. To avoid keeping everyone (={Jeff,me}?) in suspense, the proof idea is: the optimal tree (if it exists) like any spanning tree in the graph can be reached from the MST by a sequence of nondecreasing swaps. Define a flip to be a modification of this sequence consisting of doing two consecutive swaps in the opposite order.
If two swaps can not be flipped you can replace them by a different pair of swaps involving the same four edges that are still nondecreasing and can be flipped. Also, you might as well stop swapping as soon as you reach a tree with the right value mod k, since any remaining swaps in the sequence won't get you to a better tree. You can flip any zero-mod-k flips to the end of the sequence (or replace them by nonzero swaps), so you can assume there are no zeros; for k=2 this means the sequence has only one swap. For k=3 a sequence without zeros that doesn't have any parity-zero prefix must alternate between +1 and -1; if you can flip two of these alternating +1 and -1 swaps you can reduce the length of the sequence, and otherwise you can replace them by two zeros that can then be flipped to the end of the sequence.

The comments to this entry are closed.