Efficient maximal cliques enumeration in weakly closed graphs
Manoussakis, George · arXiv (Cornell University) · 2023
We show that the algorithm presented in [J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein. Finding cliques in social networks: A new distribution-free model. SIAM journal on computing, 49(2):448-464, 2020.] can be modified to have enumeration time complexity $α\mathcal{O} (npoly(c))$. Here parameter $c$ is the weakly closure of the graph and $α$ its number of maximal cliques. This result improves on their complexity which was not output sensitive and exponential in the closure of the graph.