Logo image
Back
Distributed Approximation on Power Graphs
Conference proceeding

Distributed Approximation on Power Graphs

Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus, Shreyas Pai and Sriram Pemmaraju
Proceedings of the 39th Symposium on principles of distributed computing, pp.501-510
PODC '20
07/31/2020
DOI: 10.1145/3382734.3405750
url
https://arxiv.org/pdf/2006.03746View
Open Access

Abstract

We investigate graph problems in the following setting: we are given a graph G and we are required to solve a problem on G 2 . 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 G 2 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. Specifically, we encounter two phenomena acting in opposing directions: (i) slowdown due to congestion and (ii) speedup due to structural properties of G 2 . We demonstrate these two phenomena via two fundamental graph problems, namely, Minimum Vertex Cover (MVC) and Minimum Dominating Set (MDS). Among our many contributions, the highlights are the following. (1) In the CONGEST model, we show an O ( n /∈)-round (1 + ∈)-approximation algorithm for MVC on G 2 , whereas no o ( n 2 )-round algorithm is known for any better-than-2 approximation for MVC on G. (2) We show a centralized polynomial time 5/3-approximation algorithm for MVC on G 2 , whereas a better-than-2 approximation is UGC-hard for G. (3) In contrast, for MDS, in the CONGEST model, we show an [EQUATION] lower bound for a constant approximation factor for MDS on G 2 , whereas an Ω( n 2 ) lower bound for MDS on G is known only for exact computation.

Details

Metrics

10 Record Views
Logo image