Given an undirected graph *G* where every edge has integer weight, how hard is it to compute the minimum-weight spanning tree of *G* whose total weight is a multiple of some other positive integer *k*? This is obviously trivial if *k*=1. David Eppstein quickly observed that the minimum *even* spanning tree—assuming the graph *has* a spanning tree of even total weight—differs from the minimum spanning tree by at most one edge, so this problem can be solved quickly when *k*=2. [The proof is left as an exercise for the reader.] On the other hand, if *k* is provided as part of the input, the problem is (weakly) NP-hard by a straightforward reduction from the SUBSET SUM problem. The intermediate case, where *k* is a fixed integer larger than 2, appears to be open. Is computing the minimum multiple-of-3 spanning tree NP-hard?

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

Posted by: David Eppstein | June 14, 2004 at 12:32 PM

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.

Posted by: David Eppstein | June 14, 2004 at 12:52 PM