License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.27
URN: urn:nbn:de:0030-drops-122748
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12274/
Jansen, Bart M. P. ;
de Kroon, Jari J. H.
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 ?₂ implies graph-theoretic statements about the presence of forbidden induced subgraphs.
BibTeX - Entry
@InProceedings{jansen_et_al:LIPIcs:2020:12274,
author = {Bart M. P. Jansen and Jari J. H. de Kroon},
title = {{Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {27:1--27:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-150-4},
ISSN = {1868-8969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12274},
URN = {urn:nbn:de:0030-drops-122748},
doi = {10.4230/LIPIcs.SWAT.2020.27},
annote = {Keywords: kernelization, vertex-deletion, graph modification, structural parameterization}
}
|
Keywords: |
|
kernelization, vertex-deletion, graph modification, structural parameterization |
|
Collection: |
|
17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
12.06.2020 |
