A Com­pa­ri­son of Es­ti­ma­ti­on Me­thods of the Short­cut­Qua­li­ty for Spe­­ci­fic Graph Par­ti­ti­ons

Understanding the fundamental performance limits of distributed graph algorithms is a central challenge in the design of large-scale systems such as Google's Pregel and Facebook's Giraph. A key theoretical parameter in this space is ShortcutQuality, which captures how efficiently the parts of a distributed network can communicate — but computing it is highly intractable in general. This thesis takes a first practical step toward that goal by narrowing the scope to a fixed graph partition and designing three heuristic algorithms for estimating shortcut quality efficiently. The first frames the problem as a multicommodity flow optimization; the second uses a clustering-based construction; the third builds shortcuts by iteratively adding the most important paths. Evaluated on sparse Delaunay triangulation graphs, the first and third algorithms consistently achieve provably optimal results on networks of up to 1000 nodes, while the second offers a compelling speed advantage at some quality cost. Together, these results open a concrete path toward the broader computation of ShortcutQuality.