@inproceedings{28b4f8b5989b4d3cbe6961d5dd784372,

title = "Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies",

abstract = "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 F2 implies graph-theoretic statements about the presence of forbidden induced subgraphs.",

keywords = "Graph modification, kernelization, Structural parameterization, Vertex-deletion",

author = "Jansen, {Bart M.P.} and {de Kroon}, {Jari J.H.}",

year = "2020",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SWAT.2020.27",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Susanne Albers",

booktitle = "17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020",

note = "17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020 ; Conference date: 22-06-2020 Through 24-06-2020",

}