Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs

Abstract

Given a graph \(G\) and a spanning tree \(T\) of \(G\), we say that \(T\) is a tree \(t\)-spanner of \(G\) if the distance between every pair of vertices in \(T\) is at most \(t\) times their distance in \(G\). The problem of finding a tree \(t\)-spanner minimizing \(t\) is referred to as the Minimum Max-Stretch spanning Tree (MMST) problem. This paper concerns the MMST problem on unweighted graphs. The problem is known to be NP-hard, and the paper presents an \(O(\log n)\)-approximation algorithm for it. Furthermore, it is established that unless \(\mathrm{P}=\mathrm{NP}\), the problem cannot be approximated additively by any \(o(n)\) term.