Detecting communities is hard, and counting them is even harder

We consider the algorithmic problem of community detection in networks. Given an undirected friendship graph $G=(V,E)$, a subset $S\subseteq V$ is an $(\alpha ,\beta )$-community if:

• Every member of the community is friends with an $\alpha$-fraction of the community;
• Every non-member is friends with at most a $\beta$-fraction of the community. Arora et al [AGSS12] gave a quasi-polynomial time algorithm for enumerating all the $(\alpha ,\beta )$-communities for any constants $\alpha >\beta$. Here, we prove that, assuming the Exponential Time Hypothesis (ETH), quasi-polynomial time is in fact necessary - and even for a much weaker approximation desideratum. Namely, distinguishing between:
• $G$ contains an $(1,o\left(1\right))$-community; and
• $G$ does not contain an $(\beta +o\left(1\right),\beta )$-community for any $\beta \in [0,1]$. We also prove that counting the number of $(1,o\left(1\right))$-communities requires quasi-polynomial time assuming the weaker #ETH.