Lossy kernelization

DOI10.1145/3055399.3055456zbMATH Open1370.68136arXiv1604.04111OpenAlexW2911549278MaRDI QIDQ4977974

Author name not available (Why is that?)

Publication date: 17 August 2017

Published in: (Search for Journal in Brave)

Abstract: 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 combine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size $alpha$-approximate kernel. Loosely speaking, a polynomial size $alpha$-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^{\prime },k^{\prime })$ to the same problem, such that $|I^{\prime }|+k^{\prime }leq{k}^{O(1)}$. Additionally, for every $cgeq1$, a $c$-approximate solution $s^{\prime }$ to the pre-processed instance $(I^{\prime },k^{\prime })$ can be turned in polynomial time into a $(ccdotalpha)$-approximate solution $s$ to the original instance $(I,k)$. Our main technical contribution are $alpha$-approximate kernels of polynomial size for three problems, namely Connected Vertex Cover, Disjoint Cycle Packing and Disjoint Factors. These problems are known not to admit any polynomial size kernels unless $NPsubseteqcoNP/poly$. Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size, and the hardness of approximation lower bounds for all three problems. On the negative side we prove that Longest Path parameterized by the length of the path and Set Cover parameterized by the universe size do not admit even an $alpha$-approximate kernel of polynomial size, for any $alphageq1$, unless $NPsubseteqcoNP/poly$. In order to prove this lower bound we need to combine in a non-trivial way the techniques used for showing kernelization lower bounds with the methods for showing hardness of approximation

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Lossy kernelization

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