dorsal/arxiv
View SchemaProtrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors
| Authors | Roohani Sharma, Michał Włodarczyk |
|---|---|
| Categories | |
| ArXiv ID | 2601.08424vv2 |
| URL | https://arxiv.org/abs/2601.08424 |
| DOI | 10.4230/LIPIcs.STACS.2026.31 |
| License | http://creativecommons.org/licenses/by/4.0/ |
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 & 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 & Saurabh [TALG 2017] proved that this is already inevitable for the special case of the Treewidth-d-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-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. 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 & Sikdar [TALG 2015] on graph classes that exclude a topological minor.
{
"annotation_id": "27221d26-7b58-46ce-85b9-99dcaf9bfb66",
"date_created": "2026-02-17T05:53:15.842000Z",
"date_modified": "2026-02-17T05:53:15.842000Z",
"file_hash": "6ff3e60f3d2cbd60e73fdb07400310b6d9234849677a82a229c5b5cac58adc63",
"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": "v2"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "7b849623-6730-47eb-9c04-4c2acd761436",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}