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 of distance 2 of 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 is a graph that can be made planar by the removal of at most k vertices. We prove that the generalization of Square Root, in which we are given two subsets of edges prescribed to be in or out of a square root, respectively, 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. (2016, June). A linear kernel for finding square roots of almost planar graphs. Presented at 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
• Start Date: Jun 22, 2016
• End Date: Jun 24, 2016
• Acceptance Date: Apr 1, 2016
• Publication Date: Jun 24, 2016
• Deposit Date: Jun 29, 2016
• Publicly Available Date: Jul 1, 2016
• Series Title: Leibniz International Proceedings in Informatics (LIPIcs)
• Series Number: 53
• Series ISSN: 1868-8969
• Book Title: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016).
• DOI: https://doi.org/10.4230/lipics.swat.2016.4
• Public URL: https://durham-repository.worktribe.com/output/1150184
• Additional Information: Conference date: 22-24 June 2016