2026-07-20T11:15:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8149 2024-03-06T10:39:21Z ddc:004 open_access

Detecting communities is Hard (And Counting Them is Even Harder) Rubinstein, Aviad Community detection stable communities quasipolynomial time We consider the algorithmic problem of community detection in networks. Given an undirected friendship graph G, a subset S of vertices is an (a,b)-community if: * Every member of the community is friends with an (a)-fraction of the community; and * every non-member is friends with at most a (b)-fraction of the community. [Arora, Ge, Sachdeva, Schoenebeck 2012] gave a quasi-polynomial time algorithm for enumerating all the (a,b)-communities for any constants a>b. 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(1))-community; and * G does not contain a (b,b+o(1))-community for any b. We also prove that counting the number of (1,o(1))-communities requires quasi-polynomial time assuming the weaker #ETH. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aviad Rubinstein 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.42 urn:nbn:de:0030-drops-81496 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.42 eng https://creativecommons.org/licenses/by/3.0/legalcode