Modular minimum spanning trees

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?

Comments

[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.