Polynomial kernels for 3-leaf power graph modification problems

Stephane Bessy, Christophe Paul, Anthony Perez

A graph G=(V,E) is a 3-leaf power iff there exists a tree T whose leaves are V and such that (u,v) is an edge iff u and v are at distance at most 3 in T. The 3-leaf power graph edg…