When MIS and Maximal Matching are Easy in the Congested Clique

Abstract

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 \textsf{Congested\ Clique}, with $O(\log \log \hat{I}”)$ being the best upper bound known (where $\hat{I}”$ 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 ${\hat{I}}^2(G)\le 2^{O(\sqrt{\log n})}$, or (3) the independence number is at most $\hat{I}\pm (G)\le |V(G)|/d(G{)}^{\hat{I}}¼$, for any constant $\hat{I}¼>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.

28 pages. To appear in proceedings of SIROCCO 2025