Distributed Approximation on Power Graphs
Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus, Shreyas Pai, Sriram V. Pemmaraju · 2020
We investigate graph problems in the following setting: we are given a graph G and we are required to solve a problem on G2. While we focus mostly on exploring this theme in the distributed CONGEST model, we also show new results and surprising connections to the centralized model of computation. In the CONGEST model, it is natural to expect that problems on G2 would be quite difficult to solve efficiently on G, due to congestion. However, we show that the picture is both more complicated and more interesting.