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



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 at distance 2 from 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 (or k-apex graph) is a graph that can be made planar by the removal of at most k vertices. We prove that a generalization of Square Root, in which some edges are prescribed to be either in or out of any solution, 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. (2017). A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science, 689, 36-47. https://doi.org/10.1016/j.tcs.2017.05.008

Journal Article Type Article
Acceptance Date May 11, 2017
Online Publication Date May 25, 2017
Publication Date May 25, 2017
Deposit Date May 20, 2017
Publicly Available Date Mar 29, 2024
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 689
Pages 36-47
DOI https://doi.org/10.1016/j.tcs.2017.05.008
Public URL https://durham-repository.worktribe.com/output/1378642

Files





You might also like



Downloadable Citations