2026-08-05T23:52:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14659 2024-03-06T10:54:34Z ddc:004 open_access

On Approximate Compressions for Connected Minor-Hitting Sets Ramanujan, M. S. Parameterized Complexity Kernelization Approximation Algorithms In the Connected ℱ-Deletion problem, ℱ is a fixed finite family of graphs and the objective is to compute a minimum set of vertices (or a vertex set of size at most k for some given k) such that (a) this set induces a connected subgraph of the given graph and (b) deleting this set results in a graph which excludes every F ∈ ℱ as a minor. In the area of kernelization, this problem is well known to exclude a polynomial kernel subject to standard complexity hypotheses even in very special cases such as ℱ = K₂, i.e., Connected Vertex Cover. In this work, we give a (2+ε)-approximate polynomial compression for the Connected ℱ-Deletion problem when ℱ contains at least one planar graph. This is the first approximate polynomial compression result for this generic problem. As a corollary, we obtain the first approximate polynomial compression result for the special case of Connected η-Treewidth Deletion. Schloss Dagstuhl – Leibniz-Zentrum für Informatik M. S. Ramanujan 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.78 urn:nbn:de:0030-drops-146590 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.78 eng https://creativecommons.org/licenses/by/4.0/legalcode