The Effect of Sparsity on k -Dominating Set and Related First-Order Graph Properties
Nick Fischer, Marvin Künnemann, Mirza Redžić · Society for Industrial and Applied Mathematics eBooks · 2024
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?