Abstract
Given two sets a. p of non-negative integers, a set S of vertices of a graph G is (a. p)dominating if |S boolean AND N(v)| is an element of sigma for every vertex v is an element of S. and |S boolean AND N(v)| is an element of rho for every v 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 (sigma, rho)-domination in this general setting. Among other results, we show that the existence of a (sigma, rho)-dominating set of size k (and at most k) are W[1]-complete problems (when parameterized by k) for any pair of finite sets a and p.
We further present results on dual parameterization by n - k, and results on certain infinite sets (in particular for a. p being the sets of even and odd integers).