What question did this study set out to answer?

The aim is to improve the efficiency of kernelization techniques for the ℱ-Deletion problem, particularly considering disconnected minors.

February 27, 20260 citationsOpen Access

Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors

RSRoohani SharmaNational Dairy Research Institute MWMichał WłodarczykWarsaw University of Technology

Key Points

The aim is to improve the efficiency of kernelization techniques for the ℱ-Deletion problem, particularly considering disconnected minors.
Developed a 2-approximate kernelization algorithm for Treewidth-η-Deletion with a kernel size of g(η) ⋅ k⁶.
Introduced mechanisms to achieve a close approximation factor using a bounded number of oracle calls for small instances.
Extended results to general ℱ-Deletion involving planar graphs and reachable through Treewidth-η-Deletion oracles.
Demonstrated a method that maintains a polynomial kernel size even with the inclusion of disconnected graphs.
Achieved linear kernels on sparse graph classes involving planar graph families, enhancing previous methods that required connectivity.

Abstract

Let ℱ be a finite family of graphs. In the ℱ-Deletion problem, one is given a graph G and an integer k, and the goal is to find k vertices whose deletion results in a graph with no minor from the family ℱ. This may be regarded as a far-reaching generalization of Vertex Cover and Feedback vertex Set. In their seminal work, Fomin, Lokshtanov, Misra & Saurabh FOCS 2012 gave a polynomial kernel for this problem when the family ℱ contains a planar graph. As the size of their kernel is g (ℱ) ⋅ k^f (ℱ), a natural follow-up question was whether the dependence on ℱ in the exponent of k can be avoided. The answer turned out to be negative: Giannopoulou, Jansen, Lokshtanov & Saurabh TALG 2017 proved that this is already inevitable for the special case of the Treewidth-η-Deletion problem. In this work, we show that this non-uniformity can be avoided at the expense of a small loss. First, we present a simple 2-approximate kernelization algorithm for Treewidth-η-Deletion with a kernel size g (η) ⋅ k⁶. Next, we show that the approximation factor can be made arbitrarily close to 1, if we settle for a kernelization protocol with 𝒪 (1) calls to an oracle that solves instances of size bounded by a uniform polynomial in k. We extend the above results to general ℱ-Deletion, whenever ℱ contains a planar graph, as long as an oracle for Treewidth-η-Deletion is available for small instances. Notably, all our constants are computable functions of ℱ and our techniques work also when some graphs in ℱ may be disconnected. Our results rely on two novel techniques. First, we transform so-called "near-protrusion decompositions" into true protrusion decompositions by sacrificing a small accuracy loss. Secondly, we show how to optimally compress such a decomposition with respect to general ℱ-Deletion. Using our second technique, we also obtain linear kernels on sparse graph classes when ℱ contains a planar graph, whereas the previously known theorems required all graphs in ℱ to be connected. Specifically, we generalize the kernelization algorithm by Kim, Langer, Paul, Reidl, Rossmanith, Sau & Sikdar TALG 2015 on graph classes that exclude a topological minor.

问 AI

Bookmark

View Full Paper