An improved kernelization algorithm for Trivially Perfect Editing
share
In the Trivially Perfect Editing problem one is given an undirected graph G = (V,E) and an integer k and seeks to add or delete at most k edges in G to obtain a trivially perfect graph. In a recent work, Dumas, Perez and Todinca [Algorithmica 2023] proved that this problem admits a kernel with O(k^3) vertices. This result heavily relies on the fact that the size of trivially perfect modules can be bounded by O(k^2) as shown by Drange and Pilipczuk [Algorithmica 2018]. To obtain their cubic vertex-kernel, Dumas, Perez and Todinca [Algorithmica 2023] then showed that a more intricate structure, so-called comb, can be reduced to O(k^2) vertices. In this work we show that the bound can be improved to O(k) for both aforementioned structures and thus obtain a kernel with O(k^2) vertices. Our approach relies on the straightforward yet powerful observation that any large enough structure contains unaffected vertices whose neighborhood remains unchanged by an editing of size k, implying strong structural properties.
READ FULL TEXT