2026-08-07T08:16:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12274 2024-03-06T10:49:30Z ddc:004 open_access

Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies Jansen, Bart M. P. de Kroon, Jari J. H. kernelization vertex-deletion graph modification structural parameterization We consider the Π-free Deletion problem parameterized by the size of a vertex cover, for a range of graph properties Π. Given an input graph G, this problem asks whether there is a subset of at most k vertices whose removal ensures the resulting graph does not contain a graph from Π as induced subgraph. Many vertex-deletion problems such as Perfect Deletion, Wheel-free Deletion, and Interval Deletion fit into this framework. We introduce the concept of characterizing a graph property Π by low-rank adjacencies, and use it as the cornerstone of a general kernelization theorem for Π-Free Deletion parameterized by the size of a vertex cover. The resulting framework captures problems such as AT-Free Deletion, Wheel-free Deletion, and Interval Deletion. Moreover, our new framework shows that the vertex-deletion problem to perfect graphs has a polynomial kernel when parameterized by vertex cover, thereby resolving an open question by Fomin et al. [JCSS 2014]. Our main technical contribution shows how linear-algebraic dependence of suitably defined vectors over 𝔽₂ implies graph-theoretic statements about the presence of forbidden induced subgraphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bart M. P. Jansen and Jari J. H. de Kroon 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.27 urn:nbn:de:0030-drops-122748 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.27 eng https://creativecommons.org/licenses/by/3.0/legalcode