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.
Original language | English |
---|---|
Title of host publication | 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020 |
Editors | Susanne Albers |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
ISBN (Electronic) | 9783959771504 |
DOIs | |
Publication status | Published - 1 Jun 2020 |
Event | 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020 - Torshavn, Faroe Islands Duration: 22 Jun 2020 → 24 Jun 2020 |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 162 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020 |
---|---|
Country/Territory | Faroe Islands |
City | Torshavn |
Period | 22/06/20 → 24/06/20 |
Funding
Funding This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch).
Keywords
- Graph modification
- kernelization
- Structural parameterization
- Vertex-deletion