The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs

DOI10.1137/20M1316044MaRDI QIDQ6315907arXivFDO

Authors Enric Boix-Adserà, Matthew D. Brennan, Guy Bresler

Publication date 19 March 2019

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65)

Abstract: We consider the problem of counting $k$-cliques in $s$-uniform Erdos-Renyi hypergraphs $G(n,c,s)$ with edge density $c$, and show that its fine-grained average-case complexity can be based on its worst-case complexity. We prove the following: 1. Dense Erdos-Renyi graphs and hypergraphs: Counting $k$-cliques on $G(n,c,s)$ with $k$ and $c$ constant matches its worst-case time complexity up to a $mathrmpolylog(n)$ factor. Assuming randomized ETH, it takes $n^{Omega(k)}$ time to count $k$-cliques in $G(n,c,s)$ if $k$ and $c$ are constant. 2. Sparse Erdos-Renyi graphs and hypergraphs: When $c=Theta(n^{-alpha})$, we give several algorithms exploiting the sparsity of $G(n,c,s)$ that are faster than the best known worst-case algorithms. Complementing this, based on a fine-grained worst-case assumption, our results imply a different average-case phase diagram for each fixed $alpha$ depicting a tradeoff between a runtime lower bound and $k$. Surprisingly, in the hypergraph case ($sge3$), these lower bounds are tight against our algorithms exactly when $c$ is above the ErdH{o}s-R'{e}nyi $k$-clique percolation threshold. This is the first worst-case-to-average-case hardness reduction for a problem on ErdH{o}s-R'{e}nyi hypergraphs that we are aware of. We also give a variant of our result for computing the parity of the $k$-clique count that tolerates higher error probability.

This page was built for publication: The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315907)