1 citations · 1 across the 5 of their papers we have counts for
8 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,…
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…
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…
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…
The Effect of Sparsity on -Dominating Set and Related First-Order Graph Properties
Nick Fischer, Marvin Künnemann, Mirza Redzic
We revisit -Dominating Set, one of the first problems for which a tight conditional lower bound (for ), based on SETH, was shown (Pătraşcu and Williams, SODA…