A linear kernel for finding square roots of almost planar graphs
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart · Theoretical Computer Science · 2017
A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are at distance 2 from each other. The Square Root problem is that of deciding whether a given graph admits a square root. We consider this problem for planar graphs in the context of the “distance from triviality” framework. For an integer k , a planar + k v graph (or k -apex graph) is a graph that can be made planar by the removal of at most k vertices. We prove that a generalization of Square Root , in which some edges are prescribed to be either in or out of any solution, has a kernel of size O ( k ) for planar + k v graphs, when parameterized by k . Our result is based on a new edge reduction rule which, as we shall also show, has a wider applicability for the Square Root problem.