DUAL PARAMETERIZATION AND PARAMETERIZED APPROXIMABILITY OF SUBSET GRAPH PROBLEMS

摘要

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.