Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs

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∈ 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"unnemann, 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≤ k-2, we obtain a running time of (m/n)r nk-r+o(1) that is conditionally optimal assuming the 3-uniform hyperclique hypothesis. In sparse graphs, this fully interpolates between nk-1± o(1) and n2± o(1), depending on r. Curiously, when r=k-1, we obtain a randomized algorithm beating (m/n)k-1 n1+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).