Content area
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<\frac{1}{3}n-O(1)\), the greedy algorithm is not `universally optimal'. (2) On the positive side, when \(k>\frac{2}{3}n+O(1)\), the greedy algorithm is `universally optimal'. We also introduce an appropriate notion for `approximately universal optimality'. An algorithm is \((\alpha,\beta)\)-universally optimal iff given any \(n\)-vertex input graph \(G\), it can produce a \(k\)-spanner \(H\) of \(G\) with size \(|H|\leq n+\alpha(|H^*|-n)+\beta\), where \(H^*\) is the smallest \(k\)-spanner of \(G\). We show the following positive bounds. (1) When \(k>\frac{4}{7}n+O(1)\), the greedy algorithm is \((2,O(1))\)-universally optimal. (2) When \(k>\frac{12}{23}n+O(1)\), the greedy algorithm is \((18,O(1))\)-universally optimal. (3) When \(k>\frac{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.