English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the $\Pi$-free Deletion problem parameterized by the size of avertex 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 whoseremoval ensures the resulting graph does not contain a graph from $\Pi$ asinduced subgraph. Many vertex-deletion problems such as Perfect Deletion,Wheel-free Deletion, and Interval Deletion fit into this framework. Weintroduce the concept of characterizing a graph property $\Pi$ by low-rankadjacencies, and use it as the cornerstone of a general kernelization theoremfor $\Pi$-Free Deletion parameterized by the size of a vertex cover. Theresulting framework captures problems such as AT-Free Deletion, Wheel-freeDeletion, and Interval Deletion. Moreover, our new framework shows that thevertex-deletion problem to perfect graphs has a polynomial kernel whenparameterized by vertex cover, thereby resolving an open question by Fomin etal. [JCSS 2014]. Our main technical contribution shows how linear-algebraicdependence of suitably defined vectors over $\mathbb{F}_2$ impliesgraph-theoretic statements about the presence of forbidden induced subgraphs.

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