Incompressibility of H-free edge modification problems: Towards a dichotomy

Dániel Marx, R. B. Sandeep

Given a graph $G$ and an integer $k$, the $H$-free Edge Editing problem is to find whether there exists at most $k$ pairs of vertices in $G$ such that changing the adjacency of the…