Uniform polynomial kernel for deletion to K₂,p minor-free graphs

DOI10.4230/LIPICS.ISAAC.2024.46MaRDI QIDQ7260666zbMATH OpenFDO

Authors William Lochet, Roohani Sharma

Publication date 8 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2024.46

zbMATH Keywords

\(\mathcal{F}\)-minor-free deletion\(K_{2,p}\)complete bipartite minor-free graphsprotrusionsuniform polynomial kernel

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• (Meta) kernelization
• \textsc{Planar} \(\mathcal{F}\)-\textsc{deletion}: approximation, kernelization and optimal FPT algorithms
• A characterization of \(K_{2,4}\)-minor-free graphs
• A near-optimal planarization algorithm
• Graph minors. XIII: The disjoint paths problem
• Hitting forbidden minors: approximation and kernelization
• scientific article; zbMATH DE number 5764786 (Why is no real title available?)
• Kernelization. Theory of parameterized preprocessing
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Obtaining a planar graph by vertex deletion
• Planarity Allowing Few Error Vertices in Linear Time
• Polynomial bounds for the grid-minor theorem
• Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
• The circumference of a graph with no \(K_{3,t}\)-minor
• The edge-density for \(K_{2,t}\) minors
• The extremal function for unbalanced bipartite minors
• The node-deletion problem for hereditary properties is NP-complete
• Toughness of \(K_{a,t}\)-minor-free graphs
• Uniform kernelization complexity of hitting forbidden minors

This page was built for publication: Uniform polynomial kernel for deletion to \(K_{2,p}\) minor-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7260666)