The complexity of irredundant sets parameterized by size Export

@article{citeulike:566300, abstract = {An irredundant set of vertices V\′[subset of or equal to]V in a graph G=(V,E) has the property that for every vertex u[set membership, variant]V\′, N[V\′-{u}] is a proper subset of N[V\′]. We investigate the parameterized complexity of determining whether a graph has an irredundant set of size k, where k is the parameter. The interest of this problem is that while most \“k-element vertex set\” problems are NP-complete, several are known to be fixed-parameter tractable, and others are hard for various levels of the parameterized complexity hierarchy. Complexity classification of vertex set problems in this framework has proved to be both more interesting and more difficult. We prove that the k-element irredundant set problem is complete for W[1], and thus has the same parameterized complexity as the problem of determining whether a graph has a k-clique. We also show that the \“parametric dual\” problem of determining whether a graph has an irredundant set of size n-k is fixed-parameter tractable.}, author = {Downey, Rodney G. and Fellows, Michael R. and Raman, Venkatesh}, citeulike-article-id = {566300}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0166-218X(99)00185-7}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6TYW-3YC0F6X-2/2/581d7dd9df3461c73786a5c3265ea7ae}, day = {30}, doi = {10.1016/S0166-218X(99)00185-7}, journal = {Discrete Applied Mathematics}, keywords = {irredundant\_sets, parameterized\_complexity}, month = {March}, number = {3}, pages = {155--167}, posted-at = {2006-03-27 23:27:35}, priority = {0}, title = {The complexity of irredundant sets parameterized by size}, url = {http://dx.doi.org/10.1016/S0166-218X(99)00185-7}, volume = {100}, year = {2000} }

TY - JOUR ID - citeulike:566300 L3 - citeulike-article-id:566300 N2 - An irredundant set of vertices V′[subset of or equal to]V in a graph G=(V,E) has the property that for every vertex u[set membership, variant]V′, N[V′-{u}] is a proper subset of N[V′]. We investigate the parameterized complexity of determining whether a graph has an irredundant set of size k, where k is the parameter. The interest of this problem is that while most “k-element vertex set” problems are NP-complete, several are known to be fixed-parameter tractable, and others are hard for various levels of the parameterized complexity hierarchy. Complexity classification of vertex set problems in this framework has proved to be both more interesting and more difficult. We prove that the k-element irredundant set problem is complete for W[1], and thus has the same parameterized complexity as the problem of determining whether a graph has a k-clique. We also show that the “parametric dual” problem of determining whether a graph has an irredundant set of size n-k is fixed-parameter tractable. IS - 3 JF - Discrete Applied Mathematics EP - 167 TI - The complexity of irredundant sets parameterized by size VL - 100 SP - 155 KW - irredundant_sets KW - parameterized_complexity AU - Downey, Rodney AU - Fellows, Michael AU - Raman, Venkatesh PY - 2000/03/30/ UR - http://dx.doi.org/10.1016/S0166-218X(99)00185-7 ER -