Dual parameterization and parameterized approximability of subset graph problems

Dual parameterization and parameterized approximability of subset graph problems

0.00 Avg rating0 Votes
Article ID: iaor20173834
Volume: 51
Issue: 1
Start Page Number: 261
End Page Number: 266
Publication Date: Jan 2017
Journal: RAIRO - Operations Research
Authors: ,
Keywords: graphs, heuristics
Abstract:

We discuss approximability in FPT‐time for the class of subset optimization graph problems where a feasible solution [Formula: see text] 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 [Formula: see text] where [Formula: see text] is size of the vertex set and [Formula: see text] the standard parameter. We show that under such parameterization, many of these problems, while W[[Formula: see text]]‐hard, admit parameterized approximation schemata.

Reviews

Required fields are marked *. Your email address will not be published.