2 papers
cs.DS2026
Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
Nick Fischer, Marvin Künnemann, Mirza Redzic
We revisit the classic Maximum -Coverage problem: Determine the largest number of elements that can be covered by choosing sets from a given family $\mathcal{F} = \{S_1,…
cs.CC2025
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
Nick Fischer, Marvin Künnemann, Mirza RedžiÄ +1
Is detecting a -clique in -partite regular (hyper-)graphs as hard as in the general case? Intuition suggests yes, but proving this -- especially for hypergraphs -- poses nota…