Parameterized Complexity and Approximation Algorithms

2007/03/06 by D. Marx, Dániel Marx · 288 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Complexity and Algorithms in Graphs #Computer science #Library science #Mathematical economics #Mathematics #Optimization and Search Problems #Parameterized complexity #Physics #Volume (thermodynamics)

paper · doi:10.1093/comjnl/bxm048

published in The Computer Journal 51(1), 60-78 (Oxford University Press)

openalex publication_date 2007/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/26

Abstract

Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type and propose directions for future research. 1.

Cited by

• Knapsack Problems: A Parameterized Point of View
• Lossy Kernelization
• Faster Minimum k-cut of a Simple Graph
• A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
• Parameterized Complexity of Bandwidth on Trees
• Augmenting graphs to minimize the diameter
• Lower bounds for approximation schemes for Closest String
• Subexponential and FPT-time Inapproximability of Independent Set and Related Problems
• A note on the hardness of graph diameter augmentation problems
• Breaking the 2ⁿ-Barrier for Irredundance: A Parameterized Route to Solving Exact Puzzles
• Parameterized Approximability for Modular Linear Equations
• On Approximating String Selection Problems with Outliers
• Fixed-Parameter and Approximation Algorithms: A New Look
• FPT-Approximability of Stable Matching Problems
• Exponential-Time Approximation of Hard Problems
• The Parameterized Complexity of k-Biclique
• Edge covering with budget constrains
• Approximating low-dimensional coverage problems
• Completely inapproximable monotone and antimonotone parameterized problems
• On the optimality of approximation schemes for the classical scheduling problem
• Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges
• Outlier Detection for DNA Fragment Assembly
• Parameterized (in)approximability of subset problems
• A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
• Strong Backdoors to Nested Satisfiability
• Lossy kernelization
• The Parameterized Hardness of the k-Center Problem in Transportation Networks
• Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
• Kernelization: Theory of Parameterized Preprocessing
• Sparsification and subexponential approximation
• Geometric Dominating Set and Set Cover via Local Search
• Parameterized approximability of maximizing the spread of influence in networks
• The Exponential Time Hypothesis and the Parameterized Clique Problem
• Parameterized Algorithms for Boxicity
• Parameterized approximation algorithm [wikipedia]
• Intentional communication: computationally easy or difficult? [europepmc]

Related

• A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
• 09511 Executive Summary – Parameterized complexity and approximation algorithms
• 09511 Open Problems – Parameterized complexity and approximation algorithms
• Fundamentals of Parameterized Complexity Revisited
• 09511 Abstracts Collection – Parameterized complexity and approximation algorithms