2026-07-21T19:24:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22877 2025-10-02T13:36:14Z ddc:004 open_access

Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion Houari-Durand, Séhane Bel Eiben, Eduard Wahlström, Magnus Graph modification problems parameterized complexity polynomial kernelization Given a graph G and an integer k, the H-free Edge Deletion problem asks whether there exists a set of at most k edges of G whose deletion makes G free of induced copies of H. Significant attention has been given to the kernelizability aspects of this problem - i.e., for which graphs H does the problem admit an "efficient preprocessing" procedure, known as a polynomial kernelization, where an instance I of the problem with parameter k is reduced to an equivalent instance I' whose size and parameter value are bounded polynomially in k? Although such routines are known for many graphs H where the class of H-free graphs has significant restricted structure, it is also clear that for most graphs H the problem is incompressible, i.e., admits no polynomial kernelization parameterized by k unless the polynomial hierarchy collapses. These results led Marx and Sandeep to the conjecture that H-free Edge Deletion is incompressible for any graph H with at least five vertices, unless H is complete or has at most one edge (JCSS 2022). This conjecture was reduced to the incompressibility of H-free Edge Deletion for a finite list of graphs H. We consider one of these graphs, which we dub the prison, and show that Prison-Free Edge Deletion has a polynomial kernel, refuting the conjecture. On the other hand, the same problem for the complement of the prison is incompressible. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Séhane Bel Houari-Durand and Eduard Eiben and Magnus Wahlström 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.52 urn:nbn:de:0030-drops-228770 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.52 eng https://creativecommons.org/licenses/by/4.0/legalcode