5 papers
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 in a given -node hypergraph. How is the time complexity affected by the sparsity of the input, i…
Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
BartÅomiej Dudek, Nick Fischer, Geri Gokaj +4
We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schul…
Engineering Dominating Patterns: A Fine-grained Case Study
Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic +1
The \emph{Dominating -Pattern} problem generalizes the classical -Dominating Set problem: for a fixed \emph{pattern} and a given graph , the goal is to find an induced…
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…
Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs
Marvin Künnemann, Mirza Redzic
The study of domination in graphs has led to a variety of domination problems studied in the literature. Most of these follow the following general framework: Given a graph and…