Tree deletion set has a polynomial kernel (but no OPT^ O(1) approximation)

DOI10.4230/LIPICS.FSTTCS.2014.85MaRDI QIDQ2978504zbMATH OpenOpenAlexFDO

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

Publication date 25 April 2017

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

zbMATH Keywords

feedback vertex setkernelizationlinear equationstree deletion set

Mathematics Subject Classification ID

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

Recommendations

• Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
• An FPT algorithm for Tree Deletion Set
• An FPT algorithm for tree deletion set
• Hitting forbidden minors: approximation and kernelization
• Hitting forbidden minors: approximation and kernelization

Cited in

(5)

• Polynomial kernels for deletion to classes of acyclic digraphs
• Deleting to structured trees
• An FPT algorithm for Tree Deletion Set
• An FPT algorithm for tree deletion set
• Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)

This page was built for publication: Tree deletion set has a polynomial kernel (but no \(\mathrm {OPT}^{\mathcal O(1)}\) approximation)

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