License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.4
URN: urn:nbn:de:0030-drops-60333
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6033/
Go to the corresponding LIPIcs Volume Portal

Golovach, Petr A. ; Kratsch, Dieter ; Paulusma, Daniël ; Stewart, Anthony

A Linear Kernel for Finding Square Roots of Almost Planar Graphs

pdf-format:
LIPIcs-SWAT-2016-4.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{golovach_et_al:LIPIcs:2016:6033,
  author =	{Petr A. Golovach and Dieter Kratsch and Dani{\"e}l Paulusma and Anthony Stewart},
  title =	{{A Linear Kernel for Finding Square Roots of Almost Planar Graphs}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6033},
  URN =		{urn:nbn:de:0030-drops-60333},
  doi =		{10.4230/LIPIcs.SWAT.2016.4},
  annote =	{Keywords: planar graphs, square roots, linear kernel}
}

Keywords: planar graphs, square roots, linear kernel
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI