2026-08-02T16:04:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22235 2024-12-05T15:32:41Z ddc:004 open_access

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs Künnemann, Marvin Redzic, Mirza Fine-grained complexity theory Dominating set Sparsity in graphs Conditionally optimal algorithms The study of domination in graphs has led to a variety of dominating set 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 connectivity property ϕ(S) (e.g., connectedness) is satisfied, and (2) each vertex v satisfies some domination property ρ(S, v) (e.g., there is some 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ü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, using fast matrix multiplication we devise efficient algorithms which in particular yield the following conditionally optimal running times if the matrix multiplication exponent ω is equal to 2: - r-Multiple k-Dominating Set (each vertex v must be adjacent to at least r vertices in S): If r ≤ 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± o(1)} and n^{2± 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. - 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). For all sufficiently large k, we provide algorithms with running time (m/n)m^{(k-1)/2+o(1)} for (a) and (b), and m^{k/2+o(1)} for (c). We show that these algorithms are essentially optimal under the k-Orthogonal Vectors Hypothesis (k-OVH). This is in contrast to H being the k-Star, which is susceptible only to a very limited improvement, with the best algorithm running in time n^{k-1 ± o(1)} in sparse graphs under k-OVH. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marvin Künnemann and Mirza Redzic 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.9 urn:nbn:de:0030-drops-222353 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.9 eng https://creativecommons.org/licenses/by/4.0/legalcode