Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion

Séhane Bel Houari-Durand, Eduard Eiben, Magnus Wahlström

Given a graph $G$ and an integer $k$, the $H$-free Edge Deletion problem asks whether there exists a set of at most $k$ edges of $G$ whose deletion makes $G$ free of induced copies…