2024/11/03 by Yeyuan Chen, Chen, Yeyuan
Computer Science · #05 #Combinatorics (math.CO) #Data Mining and Machine Learning Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2411.01486
openalex publication_date 2024/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The greedy algorithm adapted from Kruskal's algorithm is an efficient and folklore way to produce a k-spanner with girth at least k+2. The greedy algorithm has shown to be `existentially optimal', while it's not `universally optimal' for any constant k. Here, `universal optimality' means an algorithm can produce the smallest k-spanner H given any n-vertex input graph G. However, how well the greedy algorithm works compared to `universal optimality' is still unclear for superconstant k:=k(n). In this paper, we aim to give a new and fine-grained analysis of this problem in undirected unweighted graph setting. Specifically, we show some bounds on this problem including the following two (1) On the negative side, when k<(1)/(3)n-O(1), the greedy algorithm is not `universally optimal'. (2) On the positive side, when k>(2)/(3)n+O(1), the greedy algorithm is `universally optimal'. We also introduce an appropriate notion for `approximately universal optimality'. An algorithm is (α,β)-universally optimal iff given any n-vertex input graph G, it can produce a k-spanner H of G with size |H|≤ n+α(|H^*|-n)+β, where H^* is the smallest k-spanner of G. We show the following positive bounds. (1) When k>(4)/(7)n+O(1), the greedy algorithm is (2,O(1))-universally optimal. (2) When k>(12)/(23)n+O(1), the greedy algorithm is (18,O(1))-universally optimal. (3) When k>(1)/(2)n+O(1), the greedy algorithm is (32,O(1))-universally optimal. All our proofs are constructive building on new structural analysis on spanners. We give some ideas about how to break small cycles in a spanner to increase the girth. These ideas may help us to understand the relation between girth and spanners.