Search Results

Documents authored by Redzic, Mirza


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

Authors: Marvin Künnemann and Mirza Redzic

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)


Abstract
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.

Cite as

Marvin Künnemann and Mirza Redzic. Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{kunnemann_et_al:LIPIcs.IPEC.2024.9,
  author =	{K\"{u}nnemann, Marvin and Redzic, Mirza},
  title =	{{Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.9},
  URN =		{urn:nbn:de:0030-drops-222353},
  doi =		{10.4230/LIPIcs.IPEC.2024.9},
  annote =	{Keywords: Fine-grained complexity theory, Dominating set, Sparsity in graphs, Conditionally optimal algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail