Approximation Algorithms for Directed Weighted Spanners
Elena Grigorescu, Nithish Kumar, Young‐San Lin · Algorithmica · 2026
Abstract In the pairwise weighted spanner problem, we are given a directed graph with n vertices and k terminal vertex pairs. Each edge is assigned both a cost and a length . The goal is to find a minimum-cost subgraph in which the terminal distance constraints are satisfied. A more restricted variant of this problem was shown to be $$O(2^{{\log ^{1-\varepsilon } n}})$$ O ( 2 log 1 - ε n ) -hard to approximate under a standard complexity assumption, by Elkin and Peleg (Theory of Computing Systems, 2007). This general formulation captures many well-studied network connectivity problems, including spanners, distance preservers, and Steiner forests. For the weighted spanner problem where the edges have positive integral lengths with magnitudes polynomial in n , we show an $$\tilde{O}(n^{4/5 + \varepsilon })$$ O ~ ( n 4 / 5 + ε ) -approximation algorithm. When the edges have unit costs and lengths, the best previous algorithm gives an $$\tilde{O}(n^{3/5 + \varepsilon })$$ O ~ ( n 3 / 5 + ε ) -approximation, due to Chlamtáč, Dinitz, Kortsarz, and Laekhanukit (Transactions on Algorithms, 2020). We also consider the online setting, where the vertex pairs arrive one at a time, and edges must be added irrevocably to satisfy the distance constraints. We show an $$\tilde{O}(k^{1/2 + \varepsilon })$$ O ~ ( k 1 / 2 + ε ) -competitive algorithm. The state-of-the-art results are an $$\tilde{O}(n^{4/5})$$ O ~ ( n 4 / 5 ) -competitive algorithm when edges have unit costs and arbitrary positive lengths, and a $$\min \{\tilde{O}(k^{1/2 + \varepsilon }), \tilde{O}(n^{2/3 + \varepsilon })\}$$ min { O ~ ( k 1 / 2 + ε ) , O ~ (