The Dominating \(H\)-Pattern problem generalizes the classical \(k\)-Dominating Set problem: for a fixed pattern \(H\) and a given graph \(G\), the goal is to find an induced subgraph \(S\) of \(G\) such that (1) \(S\) is isomorphic to \(H\), and (2) \(S\) forms a dominating set in \(G\). Fine-grained complexity results show that on worstcase inputs, any significant improvement over the naive brute-force algorithm is unlikely, as this would refute the Strong Exponential Time Hypothesis. Nevertheless, a recent work by Dransfeld et al. (ESA 2025) reveals some significant improvement potential particularly in sparse graphs.

Consider the fundamental task of finding independent sets of (constant) size k in a given n-node hypergraph. How much is the time complexity affected by the sparsity of the input, i.e., the number of hyperedges m? Turán’s theorem implies that the problem is trivial if m = O(n^{2-ε}) for some ε > 0. Above that threshold (i.e., if m = Θ(n^γ) for some γ ≥ 2), we give a perhaps surprising algorithm with running time O(min{ n^({ω/3}k) + m^{k/3}, n^k}) (for k divisible by 3), which is essentially conditionally optimal for all γ ≥ 2, assuming the k-clique and 3-uniform hyperclique hypotheses (here, ω ≤ 2.372 denotes the matrix multiplication exponent). In fact, we obtain a more detailed time complexity that is sensitive to the arity distribution of the hyperedges. To study such phenomena in more generality, we study the time complexity of finding solutions of (constant) size k in sparse instances of Boolean constraint satisfaction problems, where n and m denote the number of variables and constraints, respectively. Our results include, among others: - an essentially full classification of the influence of sparsity for Boolean constraint families of binary arity. Of particular technical interest is a conditionally tight algorithm for the family consisting of the binary NAND and the binary Implication constraints, with a running time of Θ(m^{ω k/6 ± c}). - the identification of a large class of constraint families ℱ that exhibits a sharp phase transition: there is a threshold γ_ℱ such that the problem is trivial for m = O(n^{γ_ℱ-ε}), but requires essentially brute-force running time Θ(n^{k±c}) for m = Ω(n^{γ_ℱ}), assuming the 3-uniform hyperclique hypothesis. In general, we observe a rich landscape of time complexities. Notably, in many cases the combination of constraints display higher time complexity than either constraint alone.

We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schulman (FOCS'96, SICOMP'00) gave a surprising randomized algorithm to verify associativity of an operation odot: S x S -> S in optimal time O(|S|^2), they left open the problem of finding any subcubic algorithm for verifying distributivity of given operations odot, oplus: S x S -> S.

We investigate the relationship between graph parameters, which measure the complexity of the tree decompositions of a given graph. The treewidth tw(G) of a graph G measures the largest number of vertices required in a bag of every tree decomposition of G. Similarly, the tree-independence number tree-α(G) and the tree-chromatic number tree-χ(G) measure the largest independence number, respectively the largest chromatic number, required in a bag of every tree decomposition of G. Recently, Dallard, Milanič, and Štorgel asked (JCTB, 2024) whether for all graphs G it holds that tw(G)+1 ≤ tree-α(G) ⋅ tree-χ(G). We provide a negative answer for this question in a strong form: for every function f: {ℕ} → {ℕ}, there exists a graph G such that tw(G) > tree-α(G) ⋅ f(tree-χ(G)). On the other hand, we complement this result with an upper bound, by showing that tw(G)+1 ≤ tree-α(G)² ⋅ tree-χ(G) for every graph G.

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 $G$ and an integer $k$, decide if there is a set $S$ of $k$ vertices such that (1) some inner property $ϕ(S)$ (e.g., connectedness) is satisfied, and (2) each vertex $v$ satisfies some domination property $ρ(S, v)$ (e.g., there is an $s\in S$ that is adjacent to $v$). Since many real-world graphs are sparse, we seek to determine the optimal running time of such problems in both the number $n$ of vertices and the number $m$ of edges in $G$. While the classic dominating set problem admits a rather limited improvement in sparse graphs (Fischer, Künnemann, Redzic SODA'24), we show that natural variants studied in the literature admit much larger speed-ups, with a diverse set of possible running times. Specifically, we obtain conditionally optimal algorithms for: 1) $r$-Multiple $k$-Dominating Set (each vertex must be adjacent to at least $r$ vertices in $S$): If $r\le k-2$, we obtain a running time of $(m/n)^{r} n^{k-r+o(1)}$ that is conditionally optimal assuming the 3-uniform hyperclique hypothesis. In sparse graphs, this fully interpolates between $n^{k-1\pm o(1)}$ and $n^{2\pm o(1)}$, depending on $r$. Curiously, when $r=k-1$, we obtain a randomized algorithm beating $(m/n)^{k-1} n^{1+o(1)}$ and we show that this algorithm is close to optimal under the $k$-clique hypothesis. 2) $H$-Dominating Set ($S$ must induce a pattern $H$). We conditionally settle the complexity of three such problems: (a) Dominating Clique ($H$ is a $k$-clique), (b) Maximal Independent Set of size $k$ ($H$ is an independent set on $k$ vertices), (c) Dominating Induced Matching ($H$ is a perfect matching on $k$ vertices).

We revisit the classic k-Dominating Set problem. Besides its importance as perhaps the most natural W[2]-complete problem, it is among the first problems for which a tight nk-o(1) conditional lower bound (for all sufficiently large k), based on the Strong Exponential Time Hypothesis (SETH), was shown (Patrascu and Williams, SODA 2007). Notably, however, the underlying reduction creates dense graphs, raising the question: how much does the sparsity of the graph affect its fine-grained complexity?