Domination above r-independence: does sparseness help?.

摘要: Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate complexity Dominating Set when given a suitable lower-bound witness. Concretely, consider being provided with maximal r-independent set X (a in which all vertices have pairwise distance at least r + 1) along input graph G which, for >= 2, lower-bounds minimum size any dominating G. In spirit gap-parameters, parametrisation 'residual' R := V (G) \ N [X]. Our work aims to answer two questions: How does constant affect problem and restriction sparse classes help here? For base case = find that is paraNP -complete even apex- bounded-degree graphs. 3, W[2]-hard general graphs but FPT nowhere dense it admits linear kernel bounded expansion classes. 4, becomes essentially equivalent natural parameter, set.