SCS Undergraduate Thesis Topics
|Terence An||Guy Blelloch||Fast Approximation of Minimum 2-Hop Covers on Trees|
Distance queries on graphs is a fundamental problem for numerous real-world applications. Constant queries can be done with an APSP algorithm but that requires storing every pair of distances in Ω(n 2) space, whereas dynamically resolving distances requires O(m + n log(n)) time on m-edge n-vertex graphs. An algorithm that stores fewer precomputed values and reduces dynamic query time is the 2-hop labeling scheme where every vertex stores its distance (called a label) to a subset of the other vertices such that for any pair of vertices, they both have their distance to at least one vertex on their shortest path. The problem we study is minimizing the number of labels needed to correctly query distances. There is now a log(n) approximation algorithm for m-edge n-vertex graphs that runs in O(mn 3) time for this. We demonstrate this problem is NP-Complete, and we present the currently fastest algorithm which gives a log(n) approximation on n-vertex trees which runs in Θ(nlog(n)). We also prove that this the optimal runtime for any correct tree-labeling algorithm.