Dual parameterization and parameterized approximability of subset graph problems
Édouard Bonnet, Vangélis Th. Paschos · RAIRO - Operations Research · 2016
We discuss approximability in FPT-time for the class of subset optimization graph problems where a feasible solution S is a subset of the vertex set of the input graph. This class encompasses many well-known problems, such as min dominating set, min vertex cover, max independent set, min feedback vertex set. We study approximability of such problems with respect to the dual parameter n − k where n is size of the vertex set and k the standard parameter. We show that under such parameterization, many of these problems, while W[·]-hard, admit parameterized approximation schemata.