KIT | KIT-Bibliothek | Impressum | Datenschutz

The Effect of Sparsity on $k$-Dominating Set and Related First-Order Graph Properties

Fischer, Nick; Künnemann, Marvin 1; Redzic, Mirza 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

We revisit $k$-Dominating Set, one of the first problems for which a tight $n^k−o(1)$ conditional lower bound (for $k≥3$), based on SETH, was shown (Pătraşcu and Williams, SODA 2007). However, the underlying reduction creates dense graphs, raising the question: how much does the sparsity of the graph affect its fine-grained complexity?
We first settle the fine-grained complexity of $k$-Dominating Set in terms of both the number of nodes $n$ and number of edges $m$. Specifically, we show an $m^{nk−2−o(1)}$ lower bound based on SETH, for any dependence of $m$ on $n$. This is complemented by an $m^{nk−2+o(1)}$-time algorithm for all $k≥3$. For the $k=2$ case, we give a randomized algorithm that employs a Bloom-filter inspired hashing to improve the state of the art of $n^{ω+o(1)}$ to $m^{ω/2+o(1)}$. If $ω=2$, this yields a conditionally tight bound for all $k≥2$.
To study if $k$-Dominating Set is special in its sensitivity to sparsity, we consider a class of very related problems. The $k$-Dominating Set problem belongs to a type of first-order definable graph properties that we call monochromatic basic problems. These problems are the natural monochromatic variants of the basic problems that were proven complete for the class FOP of first-order definable properties (Gao, Impagliazzo, Kolokolova, and Williams, TALG 2019). ... mehr


Volltext §
DOI: 10.5445/IR/1000170182
Veröffentlicht am 22.04.2024
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2023
Sprache Englisch
Identifikator KITopen-ID: 1000170182
Vorab online veröffentlicht am 22.12.2023
Nachgewiesen in arXiv
Dimensions
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page