The complexity of irredundant sets parameterized by size

An irredundant set of vertices V′V in a graph G=(V,E) has the property that for every vertex uV′, NV′−{u}] is a proper subset of NV′]. 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 W1], 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.