2026-07-25T06:42:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19409 2024-03-06T11:03:58Z ddc:004 open_access

Approximately Interpolating Between Uniformly and Non-Uniformly Polynomial Kernels Agrawal, Akanksha Ramanujan, M. S. Lossy Kernelization Treewidth Modulator Vertex Deletion Problems The problem of computing a minimum set of vertices intersecting a finite set of forbidden minors in a given graph is a fundamental graph problem in the area of kernelization with numerous well-studied special cases. A major breakthrough in this line of research was made by Fomin et al. [FOCS 2012], who showed that the ρ-Treewidth Modulator problem (delete minimum number of vertices to ensure that treewidth is at most ρ) has a polynomial kernel of size k^g(ρ) for some function g. A second standout result in this line is that of Giannapoulou et al. [ACM TALG 2017], who obtained an f(η)k^𝒪(1)-size kernel (for some function f) for the η-Treedepth Modulator problem (delete fewest number of vertices to make treedepth at most η) and showed that some dependence of the exponent of k on ρ in the result of Fomin et al. for the ρ-Treewidth Modulator problem is unavoidable under reasonable complexity hypotheses. In this work, we provide an approximate interpolation between these two results by giving, for every ε > 0, a (1+ε)-approximate kernel of size f'(η,ρ,1/ε)⋅ k^g'(ρ) (for some functions f' and g') for the problem of deciding whether k vertices can be deleted from a given graph to obtain a graph that has elimination distance at most η to the class of graphs that have treewidth at most ρ. Graphs of treedepth η are precisely the graphs with elimination distance at most η-1 to the graphs of treewidth 0 and graphs of treewidth ρ are simply graphs with elimination distance 0 to graphs of treewidth ρ. Consequently, our result "approximately" interpolates between these two major results in this active line of research. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and M. S. Ramanujan 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.36 urn:nbn:de:0030-drops-194096 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.36 eng https://creativecommons.org/licenses/by/4.0/legalcode