2025/02/06 by Lin, Lan, Lin, Yixun
#05C05 #05C35 #90C27 #Combinatorics (math.CO) #FOS: Mathematics #G.2.1 #G.2.2
paper · doi:10.48550/arxiv.2502.03741
The tree spanner problem for a graph G is as follows: For a given integer k, is there a spanning tree T of G (called a tree k-spanner) such that the distance in T between every pair of vertices is at most k times their distance in G? The minimum k that G admits a tree k-spanner is denoted by σ(G). It is well known in the literature that determining σ(G)≤ 2 is polynomially solvable, while determining σ(G)≤ k for k≥ 4 is NP-complete. A long-standing open problem is to characterize graphs with σ(G)=3. This paper settles this open problem by proving that it is polynomially solvable.