Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)
From MaRDI portal
Publication:5741082
DOI10.1137/15M1038876zbMATH Open1341.05239arXiv1309.7891OpenAlexW2489053438MaRDI QIDQ5741082
Author name not available (Why is that?)
Publication date: 22 July 2016
Published in: (Search for Journal in Brave)
Abstract: In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G-S is a tree. The problem is NP-complete and even NP-hard to approximate within any factor of OPT^c for any constant c. In this paper we give a O(k^4) size kernel for the Tree Deletion Set problem. To the best of our knowledge our result is the first counterexample to the "conventional wisdom" that kernelization algorithms automatically provide approximation algorithms with approximation ratio close to the size of the kernel. An appealing feature of our kernelization algorithm is a new algebraic reduction rule that we use to handle the instances on which Tree Deletion Set is hard to approximate.
Full work available at URL: https://arxiv.org/abs/1309.7891
No records found.
No records found.
This page was built for publication: Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741082)
