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

Timo Fritsch, Marvin Künnemann, Mirza Redzic +1

Consider the fundamental task of finding independent sets of (constant) size $k$ in a given $n$-node hypergraph. How is the time complexity affected by the sparsity of the input, i…