Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)

DOI10.4230/LIPIcs.FSTTCS.2014.85zbMath1360.68510OpenAlexW2963795276MaRDI QIDQ2978504

Ondřej Suchý, Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh

Publication date: 25 April 2017

Full work available at URL: https://arxiv.org/pdf/1309.7891v1

zbMATH Keywords

linear equationsfeedback vertex setkernelizationtree deletion set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Polynomial kernels for deletion to classes of acyclic digraphs ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)

This page was built for publication: Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)