# Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies

arXiv: https://arxiv.org/abs/2004.08818 · HTML: https://mlsanity.com/paper/2004.08818/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2020.

## Built on by (most cited first, 1 of 1)

- [RevFFN: Memory-Efficient Full-Parameter Fine-Tuning of Mixture-of-Experts LLMs with Reversible Blocks](https://mlsanity.com/paper/2512.20920/) (2025)

## Abstract (arXiv)

We consider the Pi-free Deletion problem parameterized by the size of a vertex cover, for a range of graph properties Pi. 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 Pi 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 Pi by low-rank adjacencies, and use it as the cornerstone of a general kernelization theorem for Pi-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 mathbbF2 implies graph-theoretic statements about the presence of forbidden induced subgraphs.