Abstract

Many parameterized problems ask, given an instance and a natural number k as parameter, whether there is a solution of size k. We analyze the relationship between the complexity of such a problem and the corresponding maximality problem asking for a solution of size k maximal with respect to set inclusion. As our results show, many maximality problems increase the parameterized complexity, while “in terms of the W-hierarchy” minimality problems do not increase the complexity. We also address the corresponding construction, listing, and counting problems