Skip to main content

Research Repository

Advanced Search

A linear kernel for finding square roots of almost planar graphs

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

A linear kernel for finding square roots of almost planar graphs Thumbnail


Authors

P.A. Golovach

D. Kratsch

A. Stewart



Contributors

Rasmus Pagh
Editor

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). A linear kernel for finding square roots of almost planar graphs. In R. Pagh (Ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). https://doi.org/10.4230/lipics.swat.2016.4

Conference Name 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Conference Location Reykjavik, Iceland
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

Files





You might also like



Downloadable Citations