The nowhere-dense domination-set kernelization dichotomy

Let C\mathcal{C} be a class of graphs closed under taking subgraphs. A class is nowhere dense if it belongs to the sparse graph-class regime characterized by excluding arbitrarily large clique subdivisions at bounded depths; it is somewhere dense otherwise. The \textsc{Distance-rr Dominating Set} problem asks whether a given graph has a dominating set whose vertices are within distance rr of every vertex.

The nowhere-dense domination-set kernelization dichotomy. If C\mathcal{C} is nowhere dense, then for each rNr\in\mathbb{N}, the \textsc{Distance-rr Dominating Set} problem admits an almost linear kernel on C\mathcal{C}. Otherwise, if C\mathcal{C} is somewhere dense, then for some rNr\in\mathbb{N}, the \textsc{Distance-rr Dominating Set} problem is W[2]\mathsf{W}[2]-hard.

The second direction was already known for somewhere dense classes closed under taking subgraphs, while the conjectured extension of almost-linear kernelization from domination radius one to every fixed radius would establish the claimed dichotomy for parameterized complexity.

Sources & referencesView supporting material

Primary source

Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michał Pilipczuk, Roman Rabinovich and Sebastian Siebertz, “Neighborhood complexity and kernelization for nowhere dense classes of graphs”, arXiv:1612.08197 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.