Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publication17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020
EditorsSusanne Albers
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959771504
DOIs
Publication statusPublished - 1 Jun 2020
Event17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020 - Torshavn, Faroe Islands
Duration: 22 Jun 202024 Jun 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume162
ISSN (Print)1868-8969

Conference

Conference17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020
CountryFaroe Islands
CityTorshavn
Period22/06/2024/06/20

Keywords

  • Graph modification
  • kernelization
  • Structural parameterization
  • Vertex-deletion

Fingerprint Dive into the research topics of 'Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies'. Together they form a unique fingerprint.

Cite this