A linear kernel for finding square roots of almost planar graphs

作者：Golovach Petr A; Kratsch Dieter; Paulusma Daniel^*; Stewart Anthony

来源：Theoretical Computer Science, 2017, 689: 36-47.

DOI：10.1016/j.tcs.2017.05.008

• Square root
• k-apex graphs
• Linear kernel

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+kv 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 0 (k) for planar+kv 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.

• 出版日期2017-8-15