Rg. Downey et Mr. Fellows, THRESHOLD DOMINATING SETS AND AN IMPROVED CHARACTERIZATION OF W[2], Theoretical computer science, 209(1-2), 1998, pp. 123-140
Citations number
16
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
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.