2026-07-20T11:02:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6033 2024-03-06T10:37:28Z ddc:004 open_access

A Linear Kernel for Finding Square Roots of Almost Planar Graphs Golovach, Petr A. Kratsch, Dieter Paulusma, Daniël Stewart, Anthony planar graphs square roots 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr A. Golovach and Dieter Kratsch and Daniël Paulusma and Anthony Stewart 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.4 urn:nbn:de:0030-drops-60333 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.4 eng https://creativecommons.org/licenses/by/3.0/legalcode