Parameterized (in)approximability of subset problems

DOI10.1016/J.ORL.2014.03.005MaRDI QIDQ1785218zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, Vangelis Th. Paschos

Publication date 28 September 2018

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

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

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)

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.

Recommendations

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

Cites work

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

Cited in

(6)

• On the existence of subexponential parameterized algorithms
• Dual parameterization and parameterized approximability of subset graph problems
• Inapproximability results for set splitting and satisfiability problems with no mixed clauses
• Subexponential parameterized algorithms
• Computability of width of submodular partition functions
• On Parameterized Approximability

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)