2026-07-23T16:05:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23455 2025-10-02T12:55:37Z ddc:004 open_access

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs Fischer, Nick Künnemann, Marvin Redžić, Mirza Stieß, Julian fine-grained complexity theory clique detections in hypergraphs constraint satisfaction parameterized algorithms 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 ≤ 1, we obtain a linear-time solvable problem, if d = 2, the time complexity is essentially equivalent to k-clique detection, and if d ≥ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nick Fischer and Marvin Künnemann and Mirza Redžić and Julian Stieß 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.78 urn:nbn:de:0030-drops-234559 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.78 eng https://creativecommons.org/licenses/by/4.0/legalcode