  The congested clique model is a message-passing model of distributed
computation where the underlying communication network is the complete graph of
$n$ nodes. In this paper we consider the situation where the joint input to the
nodes is an $n$-node labeled graph $G$, i.e., the local input received by each
node is the indicator function of its neighborhood in $G$. Nodes execute an
algorithm, communicating with each other in synchronous rounds and their goal
is to compute some function that depends on $G$. In every round, each of the
$n$ nodes may send up to $n-1$ different $b$-bit messages through each of its
$n-1$ communication links. We denote by $R$ the number of rounds of the
algorithm. The product $Rb$, that is, the total number of bits received by a
node through one link, is the cost of the algorithm.
  The most difficult problem we could attempt to solve is the reconstruction
problem, where nodes are asked to recover all the edges of the input graph $G$.
Formally, given a class of graphs $\mathcal G$, the problem is defined as
follows: if $G \notin {\mathcal G}$, then every node must reject; on the other
hand, if $G \in {\mathcal G}$, then every node must end up, after the $R$
rounds, 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 $\Omega(\log|\mathcal{G}_n|/n)$, where $\mathcal{G}_n$ is the subclass of
all $n$-node labeled graphs in $\mathcal G$. In this paper we prove that
previous bound is tight and that it is possible to achieve it with only $R=2$
rounds. 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.
