The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
For complexity theorists, this provides a regularization tool to simplify hardness proofs and resolves the fine-grained complexity of a class of Boolean CSPs.
The paper shows that detecting k-cliques in regular hypergraphs is as hard as in general hypergraphs, establishing a fine-grained equivalence. Using this, they fully characterize the complexity of optimizing Boolean CSPs over assignments with k non-zeros, showing linear-time for degree ≤1, k-clique equivalence for degree 2, and exhaustive search for degree ≥3 under the 3-uniform hyperclique hypothesis.
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 notable challenges. Concretely, we consider a strong notion of regularity in $h$-uniform hypergraphs, where we essentially require that any subset of at most $h-1$ is incident to a uniform number of hyperedges. Such notions are studied intensively in the combinatorial block design literature. We show that any $f(k)n^{g(k)}$-time algorithm for detecting $k$-cliques in such graphs transfers to an $f'(k)n^{g(k)}$-time algorithm for the general case, establishing a fine-grained equivalence between the $h$-uniform hyperclique hypothesis and its natural regular analogue. Equipped with this regularization result, we then fully resolve the fine-grained complexity of optimizing Boolean constraint satisfaction problems over assignments with $k$ non-zeros. Our characterization depends on the maximum degree $d$ of a constraint function. Specifically, if $d\le 1$, we obtain a linear-time solvable problem, if $d=2$, the time complexity is essentially equivalent to $k$-clique detection, and if $d\ge 3$ the problem requires exhaustive-search time under the 3-uniform hyperclique hypothesis. To obtain our hardness results, the regularization result plays a crucial role, enabling a very convenient approach when applied carefully. We believe that our regularization result will find further applications in the future.