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

Parameterized algorithms · Graph algorithms

An advanced research talk, for graduate students and up.

Abstract

Draft, not yet checked by me

A 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.

Where I have given it

All appearances