3 ms·

If you modify the problem to allow passing by a node that you've already visited then the spanning tree approximation works for all graphs.