1 citations · 1 across the 5 of their papers we have counts for
5 papers · 1 filter
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…
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…