A linear kernel for finding square roots of almost planar graphs

Golovach, P.A.; Kratsch, D.; Paulusma, D.; Stewart, A.

Abstract

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.

Citation

Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2017). A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science, 689, 36-47. https://doi.org/10.1016/j.tcs.2017.05.008

• Journal Article Type: Article
• Acceptance Date: May 11, 2017
• Online Publication Date: May 25, 2017
• Publication Date: May 25, 2017
• Deposit Date: May 20, 2017
• Publicly Available Date: May 25, 2018
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 689
• Pages: 36-47
• DOI: https://doi.org/10.1016/j.tcs.2017.05.008
• Public URL: https://durham-repository.worktribe.com/output/1378642