7 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…
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,…
On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs
Alex Koutsoutis, Kilian Krause, Chun-Hung Liu +2
We investigate two recently introduced graph parameters, both of which measure the complexity of the tree decompositions of a given graph. Recall that the treewidth o…
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…