English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We revisit $k$-Dominating Set, one of the first problems for which a tight$n^k-o(1)$ conditional lower bound (for $k\ge 3$), based on SETH, was shown(P\u{a}tra\c{s}cu and Williams, SODA 2007). However, the underlying reductioncreates dense graphs, raising the question: how much does the sparsity of thegraph affect its fine-grained complexity?  We first settle the fine-grained complexity of $k$-Dominating Set in terms ofboth the number of nodes $n$ and number of edges $m$. Specifically, we show an$mn^{k-2-o(1)}$ lower bound based on SETH, for any dependence of $m$ on $n$.This is complemented by an $mn^{k-2+o(1)}$-time algorithm for all $k\ge 3$. Forthe $k=2$ case, we give a randomized algorithm that employs a Bloom-filterinspired hashing to improve the state of the art of $n^{\omega+o(1)}$ to$m^{\omega/2+o(1)}$. If $\omega=2$, this yields a conditionally tight bound forall $k\ge 2$.  To study if $k$-Dominating Set is special in its sensitivity to sparsity, weconsider a class of very related problems. The $k$-Dominating Set problembelongs to a type of first-order definable graph properties that we callmonochromatic basic problems. These problems are the natural monochromaticvariants of the basic problems that were proven complete for the class FOP offirst-order definable properties (Gao, Impagliazzo, Kolokolova, and Williams,TALG 2019). We show that among these problems, $k$-Dominating Set is the onlyone whose fine-grained complexity decreases in sparse graphs. Only for thespecial case of reflexive properties, is there an additional basic problem thatcan be solved faster than $n^{k\pm o(1)}$ on sparse graphs.  For the natural variant of distance-$r$ $k$-dominating set, we obtain ahardness of $n^{k-o(1)}$ under SETH for every $r\ge 2$ already on sparsegraphs, which is tight for sufficiently large $k$.

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