The nowhere-dense domination-set kernelization dichotomy
The nowhere-dense domination-set kernelization dichotomy
Let 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- Dominating Set} problem asks whether a given graph has a dominating set whose vertices are within distance of every vertex.
The nowhere-dense domination-set kernelization dichotomy. If is nowhere dense, then for each , the \textsc{Distance- Dominating Set} problem admits an almost linear kernel on . Otherwise, if is somewhere dense, then for some , the \textsc{Distance- Dominating Set} problem is -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.