P.A. Golovach
A linear kernel for finding square roots of almost planar graphs
Golovach, P.A.; Kratsch, D.; Paulusma, D.; Stewart, A.
Authors
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
Published Conference Proceeding
(525 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, and Anthony Stewart; licensed under Creative Commons License CC-BY
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search