A new paper titled “Greedy Algorithms for Shortcut Sets and Hopsets” has been published on arXiv. The authors are Ben Bals, Joakim Blikstad, Greg Bodwin, Daniel Dadush, Sebastian Forster, and Yasamin Nazari.

Abstract: We explore the power of greedy algorithms for hopsets and shortcut sets. In particular, we propose simplegreedy algorithms that, given an input graph 𝐺 and a parameter 𝛽, compute a shortcut set or an exact hopset 𝐻 ofhopbound at most 𝛽, and we prove the following guarantees about the size |𝐻| of the output:

For shortcut sets, we prove the bound

This matches the current state-of-the-art upper bound by Kogan and Parter [SODA ’22].• For exact hopsets of 𝑛-node, 𝑚-edge weighted graphs, the size of the output hopset is existentially optimalup to subpolynomial factors, under some technical assumptions.Despite their simplicity and conceptual implications, these greedy algorithms are slower than existing samplingbasedapproaches. Our second set of results focus on faster deterministic algorithms that are based on a certaingreedy set cover approximation algorithm on paths in the transitive closure. One consequence is a deterministicalgorithm that takes  time to compute a shortcut set of size and hopbound .

Read the article:  Greedy Algorithms for Shortcut Sets and Hopsets