On the (non-)existence of polynomial kernels for Pl-free edge modification problems

Sylvain Guillemot, Christophe Paul, Anthony Perez

Given a graph G = (V,E) and an integer k, an edge modification problem for a graph property P consists in deciding whether there exists a set of edges F of size at most k such that…