Golovach, P.A. and Kratsch, D. and Paulusma, D. and Stewart, A. (2017) 'A linear kernel for finding square roots of almost planar graphs.', Theoretical computer science., 689 . pp. 36-47.
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 O(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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (391Kb)
|Publisher Web site:||https://doi.org/10.1016/j.tcs.2017.05.008|
|Publisher statement:||© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|Date accepted:||11 May 2017|
|Date deposited:||23 May 2017|
|Date of first online publication:||25 May 2017|
|Date first made open access:||25 May 2018|
Save or Share this output
|Look up in GoogleScholar|