Given once, 2013
Hardness of r-Dominating Set on Graphs of Diameter (r+1)
Small diameter does not save you, since r-domination stays W[2]-hard at diameter r + 1
An advanced research talk, for graduate students and up.
Abstract
Draft, not yet checked by meA dominating set hits every vertex or one of its neighbours; an r-dominating set only asks that every vertex has something within distance r of it. Finding a small one is W[2]-hard in general. Does small diameter help? On graphs of diameter at most r, a single vertex already r-dominates everything, so the problem is trivial. I show that one extra unit of diameter brings full hardness back: Dominating Set is W[2]-hard on graphs of diameter 2, and r-Dominating Set is W[2]-hard on graphs of diameter r + 1 for every fixed r. The reduction embeds split graphs into a Hamming-graph wireframe and also handles the connected variant.
The slides
The viewer needs JavaScript; the PDF below works without it.