2017/06/15 by Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan +1 · 4 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Machine Learning and Algorithms
paper · doi:10.1145/3055399.3055456
openalex publication_date 2017/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions com- bine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size α-approximate kernel. Loosely speaking, a polynomial size α-approximate kernel is a polynomial time pre-processing algorithm that takes as input an instance (I, k) to a parameterized problem, and outputs another instance (I′,k′) to the same problem, such that |I′| + k′ ≤ kO(1). Additionally, for every c ≥ 1, a c-approximate solution s′ to the pre-processed instance (I′, k′) can be turned in polynomial time into a (c · α)-approximate solution s to the original instance (I,k).