Corrupted distances, still a near-optimal spanning tree: logarithmic approximation under arbitrary tampering, with no true-distance queries

Under unrestricted corruption, where distances may be raised or lowered arbitrarily, the corrupted distances alone suffice to output a spanning tree whose expected true cost is within a logarithmic factor of the true minimum spanning tree, settling a previously open question. Previously only a lower bound was known: even with adaptive point selection and true-distance probes, no algorithm could beat a logarithmic factor, while no nontrivial upper bound existed. The factor matches the existing information-theoretic lower bound, so it cannot be improved while observing only corrupted distances; the result also confirms the conjecture of the model's proposers.

The method finds an almost-dominating spanning tree on the corrupted distances and returns its path shortcut. A dominating tree requires every pair's tree distance to be at most its observed direct distance; arbitrary increases break this, so the requirement is relaxed to hold for all but a small fraction of pairs inside any sufficiently large set. The analysis rests on a high-probability event that inside any sufficiently large set only a small fraction of edges are corrupted, guaranteeing an almost-dominating tree of uncorrupted edges with near-optimal cost.

The three corruption directions differ in achievable approximation: increase-only admits a constant factor in polynomial time, while decrease-only and unrestricted reach a logarithmic factor. Under decrease-only corruption, taking the minimum spanning tree of the corrupted distances can fail badly, since the adversary can lower cross-cluster distances and induce a wrong structure. A quasi-polynomial-time algorithm reaches a smaller polylogarithmic factor for decrease-only, with evidence that polynomial time is unlikely to achieve it; increase-only simply returns the minimum spanning tree of the corrupted distances.

The results apply to metric spaces where each pairwise distance is independently corrupted with fixed constant probability and the algorithm reads only corrupted distances; apart from the quasi-polynomial algorithm, the algorithms are deterministic and expectations are over the random corrupted set. No efficient algorithm is known for the general increase-decrease model, which is explicitly left open.

For decrease-only corruption, a polynomial-time polylogarithmic approximation is argued unlikely, based on the hardness of distinguishing colorable graphs from a quietly planted distribution; this is evidence rather than a theorem. Efficient algorithms for general corruption remain unknown, and no logarithmic approximation is possible when the corruption probability is large.