{
  "annotation_id": "1a149e15-4bee-4e2b-8764-10f9b7111213",
  "date_created": "2026-02-17T05:53:15.842000Z",
  "date_modified": "2026-02-17T05:53:15.842000Z",
  "file_hash": "147885fa4a2f34e9e82fceab9b450acc19f7df368a6efb70f7ed5a7c68e50ea3",
  "private": false,
  "record": {
    "abstract": "Let F be a finite family of graphs. In the F-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 F. This may be regarded as a far-reaching generalization of Vertex Cover and Feedback vertex Set. In their seminal work, Fomin, Lokshtanov, Misra \u0026 Saurabh [FOCS 2012] gave a polynomial kernel for this problem when the family F contains a planar graph. As the size of their kernel is g(F) * k^{f(F)}, a natural follow-up question was whether the dependence on F in the exponent of k can be avoided. The answer turned out to be negative: Giannapoulou, Jansen, Lokshtanov \u0026 Saurabh [TALG 2017] proved that this is already inevitable for the special case of the Treewidth-d-Deletion problem.\n  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-d-Deletion with kernel size g(d) * k^5. Next, we show that the approximation factor can be made arbitrarily close to 1, if we settle for a kernelization protocol with O(1) calls to an oracle that solves instances of size bounded by a uniform polynomial in k.\n  We also obtain linear kernels on sparse graph classes when F contains a planar graph, whereas the previously known theorems required all graphs in F to be connected. Specifically, we generalize the kernelization algorithm by Kim, Langer, Paul, Reidl, Rossmanith, Sau \u0026 Sikdar [TALG 2015] on graph classes that exclude a topological minor.",
    "arxiv_id": "2601.08424",
    "authors": [
      "Roohani Sharma",
      "Micha\u0142 W\u0142odarczyk"
    ],
    "categories": [
      "cs.DS"
    ],
    "doi": "10.4230/LIPIcs.STACS.2026.31",
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "title": "Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors",
    "url": "https://arxiv.org/abs/2601.08424",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "56ec5416-eee1-4241-aeab-cd73d6ecf8e3",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}