Domination above r-independence: does sparseness help?

Carl Einarson, Felix Reidl

Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a suitable lower-bound…