2026-07-22T14:18:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26483 2026-07-01T07:16:12Z ddc:004 open_access

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs? Fritsch, Timo Künnemann, Marvin Redzic, Mirza Stieß, Julian Multivariate algorithmics fine-grained complexity theory classification theorems algorithmic hypergraph theory Consider the fundamental task of finding independent sets of (constant) size k in a given n-node hypergraph. How much is the time complexity affected by the sparsity of the input, i.e., the number of hyperedges m? Turán’s theorem implies that the problem is trivial if m = O(n^{2-ε}) for some ε > 0. Above that threshold (i.e., if m = Θ(n^γ) for some γ ≥ 2), we give a perhaps surprising algorithm with running time O(min{ n^({ω/3}k) + m^{k/3}, n^k}) (for k divisible by 3), which is essentially conditionally optimal for all γ ≥ 2, assuming the k-clique and 3-uniform hyperclique hypotheses (here, ω ≤ 2.372 denotes the matrix multiplication exponent). In fact, we obtain a more detailed time complexity that is sensitive to the arity distribution of the hyperedges. To study such phenomena in more generality, we study the time complexity of finding solutions of (constant) size k in sparse instances of Boolean constraint satisfaction problems, where n and m denote the number of variables and constraints, respectively. Our results include, among others: - an essentially full classification of the influence of sparsity for Boolean constraint families of binary arity. Of particular technical interest is a conditionally tight algorithm for the family consisting of the binary NAND and the binary Implication constraints, with a running time of Θ(m^{ω k/6 ± c}). - the identification of a large class of constraint families ℱ that exhibits a sharp phase transition: there is a threshold γ_ℱ such that the problem is trivial for m = O(n^{γ_ℱ-ε}), but requires essentially brute-force running time Θ(n^{k±c}) for m = Ω(n^{γ_ℱ}), assuming the 3-uniform hyperclique hypothesis. In general, we observe a rich landscape of time complexities. Notably, in many cases the combination of constraints display higher time complexity than either constraint alone. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timo Fritsch and Marvin Künnemann and Mirza Redzic and Julian Stieß 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.94 urn:nbn:de:0030-drops-264836 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.94 eng https://creativecommons.org/licenses/by/4.0/legalcode