Parameterized complexity of generalized domination problems

Given two sets σ,ρσ,ρ of non-negative integers, a set SS of vertices of a graph GG is (σ,ρ)(σ,ρ)-dominating   if |S∩N(v)|∈σ|S∩N(v)|∈σ for every vertex v∈Sv∈S, and |S∩N(v)|∈ρ|S∩N(v)|∈ρ for every v∉Sv∉S. This concept, introduced by Telle in 1990’s, generalizes and unifies several variants of graph domination studied separately before. We study the parameterized complexity of (σ,ρ)(σ,ρ)-domination in this general setting. Among other results, we show that the existence of a (σ,ρ)(σ,ρ)-dominating set of size kk (and at most kk) are W[1]-complete problems (when parameterized by kk) for any pair of finite sets σσ and ρρ. We further present results on dual parameterization by n−kn−k, and results on certain infinite sets (in particular for σ,ρσ,ρ being the sets of even and odd integers).