When Does Sparsity Help for k k -Independent Set in Hypergraphs and Other Boolean CSPs?

Timo Fritsch, Marvin Künnemann, Mirza Redzic, Julian Stieß · 2026

Read When Does Sparsity Help for k k -Independent Set in Hypergraphs and Other Boolean CSPs? by Timo Fritsch, Marvin Künnemann, Mirza Redzic, Julian Stieß (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-10778.txt.

Description

Timo Fritsch, Marvin Künnemann, Mirza Redzic, and Julian Stieß ask when sparse inputs make hard search problems easier, starting with independent sets in hypergraphs. Sparsity counts the hyperedges against the nodes, and Turán's theorem already settles very sparse cases, leaving a wide middle ground unexplored.

Above that threshold the team gives a fast algorithm whose running time is essentially optimal under standard clique hypotheses, with finer detail keyed to hyperedge sizes. They extend the study to sparse Boolean constraint problems, classifying where sparsity helps and where it does not. Algorithm designers get a near-complete map of sparsity's power for fixed-size solution search.

Catalog record

CREATORTimo Fritsch, Marvin Künnemann, Mirza Redzic, Julian Stieß
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE159352
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.10778

Browse the full library · About the Tower of Babel