Threshold dominating sets and an improved characterization of W[2]

The THRESHOLD DOMINATING SET problem is that of determining for a graph G = (V,E) whether there is a subset V' subset of or equal to V of size k, such that for each vertex v is an element of V there are at least r elements of the closed neighborhood N[v] that belong to V'. We consider the complexity of the problem parameterized by the pair (k,r). It is trivial to observe that this is hard for W[2]. It can also be easily shown to belong to a natural extension W*[2] of W[2] defined in terms of circuit families of depth bounded by a function of the parameter. We prove membership in W[2] and thus W[2]-completeness. Using this as a starting point, we prove that W*[2] = W[2]. (C) 1998-Elsevier Science B.V. All rights reserved.