# Two rounds are enough for reconstructing any graph (Class) in the congested clique model

Pedro Montealegre, Sebastian Perez-Salazar, Ivan Rapaport, Ioan Todinca

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

2 Citas (Scopus)

## Resumen

In this paper we study the reconstruction problem in the congested clique model. In the reconstruction problem nodes are asked to recover all the edges of the input graph G. Formally, given a class of graphs G, the problem is defined as follows: if (formula presented), then every node must reject; on the other hand, if (formula presented), then every node must end up knowing all the edges of G. It is not difficult to see that the cost Rb of any algorithm that solves this problem (even with public coins) is at least (formula presented), where G n is the subclass of all n-node labeled graphs in G, R is the number of rounds and b is the bandwidth. We prove here that the lower bound above is in fact tight and that it is possible to achieve it with only R = 2 rounds and private coins. More precisely, we exhibit (i) a one-round algorithm that achieves this bound for hereditary graph classes; and (ii) a two-round algorithm that achieves this bound for arbitrary graph classes. Later, we show that the bound (formula presented) cannot be achieved in one round for arbitrary graph classes, and we give tight algorithms for that case. From (i) we recover all known results concerning the reconstruction of graph classes in one round and bandwidth O(log n): forests, planar graphs, cographs, etc. But we also get new one-round algorithms for other hereditary graph classes such as unit-disc graphs, interval graphs, etc. From (ii), we can conclude that any problem restricted to a class of graphs of size 2 O(n log n) can be solved in the congested clique model in two rounds, with bandwidth O(log n). Moreover, our general two-round algorithm is valid for any set of labeled graphs, not only for graph classes.

Idioma original Inglés 25th International Colloquium, SIROCCO 2018, Revised Selected Papers Zvi Lotker, Boaz Patt-Shamir Springer Verlag 134-148 15 9783030013240 https://doi.org/10.1007/978-3-030-01325-7_15 Publicada - 2018 Sí 25th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2018 - Ma’ale HaHamisha, IsraelDuración: 18 jun. 2018 → 21 jun. 2018

### Serie de la publicación

Nombre Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11085 0302-9743 1611-3349

### Conferencia

Conferencia 25th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2018 Israel Ma’ale HaHamisha 18/06/18 → 21/06/18

## Huella

Profundice en los temas de investigación de 'Two rounds are enough for reconstructing any graph (Class) in the congested clique model'. En conjunto forman una huella única.