2026-08-16T20:57:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4826 2024-03-06T10:35:23Z ddc:004 open_access

Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation) Giannopoulou, Archontia C. Lokshtanov, Daniel Saurabh, Saket Suchy, Ondrej Tree Deletion Set Feedback Vertex Set Kernelization Linear Equations 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 an O(k^5) size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new reduction rule, based on system of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Archontia C. Giannopoulou and Daniel Lokshtanov and Saket Saurabh and Ondrej Suchy 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.85 urn:nbn:de:0030-drops-48261 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.85 eng https://creativecommons.org/licenses/by/3.0/legalcode