When MIS and Maximal Matching are Easy in the Congested Clique

Two of the most fundamental distributed symmetry-breaking problems are that of finding a maximal independent set (MIS) and a maximal matching (MM) in a graph. It is a major open question whether these problems can be solved in constant rounds of the all-to-all communication model of $\mathsf{\text{Congested}}\mathsf{\text{Clique}}$, with $O(\log \log \mathrm{\Delta })$ being the best upper bound known (where $\mathrm{\Delta }$ is the maximum degree). We explore in this paper the boundary of the feasible, asking for \emph{which graphs} we can solve the problems in constant rounds. We find that for several graph parameters, ranging from sparse to highly dense graphs, the problems do have a constant-round solution. In particular, we give algorithms that run in constant rounds when: (1) the average degree is at most $d(G)\le 2^{O(\sqrt{\log n})}$, (2) the neighborhood independence number is at most $\beta (G)\le 2^{O(\sqrt{\log n})}$, or (3) the independence number is at most $\alpha (G)\le \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}d(G{)}^{\mu }$, for any constant $\mu >0$. Further, we establish that these are tight bounds for the known methods, for all three parameters, suggesting that new ideas are needed for further progress.