Parameterized (in)approximability of subset problems

DOI10.1016/J.ORL.2014.03.005zbMATH Open1408.68067arXiv1310.5576OpenAlexW2154918515MaRDI QIDQ1785218FDOQ1785218

Authors: Édouard Bonnet, Vangelis Th. Paschos 

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Abstract: We discuss approximability and inapproximability in FPT-time for a large class of subset problems where a feasible solution $S$ is a subset of the input data and the value of $S$ is $|S|$. The class handled encompasses many well-known graph, set, or satisfiability problems such as Dominating Set, Vertex Cover, Set Cover, Independent Set, Feedback Vertex Set, etc. In a first time, we introduce the notion of intersective approximability that generalizes the one of safe approximability and show strong parameterized inapproximability results for many of the subset problems handled. Then, we study approximability of these problems with respect to the dual parameter $n-k$ where $n$ is the size of the instance and $k$ the standard parameter. More precisely, we show that under such a parameterization, many of these problems, while W[$cdot$]-hard, admit parameterized approximation schemata.

Full work available at URL: https://arxiv.org/abs/1310.5576

Recommendations

• Dual parameterization and parameterized approximability of subset graph problems
• On Parameterized Approximability
• On subexponential and FPT-time inapproximability
• On subexponential and FPT-time inapproximability
• Fixed-Parameter and Approximation Algorithms: A New Look

zbMATH Keywords

graphcomplexityapproximationparameterized algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Parameterized Approximation Problems
• Vertex packings: Structural properties and algorithms
• Non deterministic polynomial optimization problems and their approximations
• On Parameterized Approximability
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• On the max min vertex cover problem
• Safe approximation and its relation to kernelization

Cited In (8)

• Parameterized and approximation complexity of \textsc{Partial VC Dimension}
• Dual parameterization and parameterized approximability of subset graph problems
• Subexponential parameterized algorithms
• Computability of width of submodular partition functions
• On the existence of subexponential parameterized algorithms
• On Parameterized Approximability
• Inapproximability results for set splitting and satisfiability problems with no mixed clauses
• On subexponential and FPT-time inapproximability

This page was built for publication: Parameterized (in)approximability of subset problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785218)