THRESHOLD DOMINATING SETS AND AN IMPROVED CHARACTERIZATION OF W[2]

The THRESHOLD DOMINATING SET problem is that of determining for a grap h G = (V,E) whether there is a subset V' subset of or equal to V of si ze k, such that for each vertex v is an element of V there are at leas t r elements of the closed neighborhood N[v] that belong to V'. We con sider the complexity of the problem parameterized by the pair (k,r). I t is trivial to observe that this is hard for W[2]. It can also be eas ily shown to belong to a natural extension W[2] of W[2] defined in te rms of circuit families of depth bounded by a function of the paramete r. 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 Sci ence B.V. All rights reserved.