The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs

Nick Fischer, Marvin Künnemann, Mirza Redžić +1

Is detecting a $k$-clique in $k$-partite regular (hyper-)graphs as hard as in the general case? Intuition suggests yes, but proving this -- especially for hypergraphs -- poses nota…