06003520

j

06003520 Brakerski, Zvika Patt-Shamir, Boaz Distributed discovery of large near-cliques. Distrib. Comput. 24, No. 2, 79-89 (2011). 2011 Springer-Verlag, Berlin EN subgraph discovering cliques synchronous network algorithm probability of success probability of failure dense graph detection

doi:10.1007/s00446-011-0132-x

Summary: Given an undirected graph and $0\leq\epsilon\leq 1$, a set of nodes is called an $\epsilon$-near clique if all but an $\epsilon$ fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size $\epsilon$-near clique if there exists an $\epsilon^{3}$-near clique of linear size in the graph. The algorithm uses messages of $O(\log n)$ bits. The failure probability can be reduced to $n ^{-\Omega (1)}$ by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of size $\Omega (n/(\log \log n)^{ \alpha})$ for some $\alpha \in (0,1)$. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.