Skip to main content

Research Repository

Advanced Search

Finding cactus roots in polynomial time

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

Finding cactus roots in polynomial time Thumbnail


P.A. Golovach

D. Kratsch

A. Stewart


A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The SQUARE ROOT problem is that of deciding whether a given graph admits a square root. The problem of testing whether a graph admits a square root which belongs to some specified graph class H is called the H-SQUARE ROOT problem. By showing boundedness of treewidth we prove that SQUARE ROOT is polynomial-time solvable on some classes of graphs with small clique number and that H-SQUARE ROOT is polynomial-time solvable when H is the class of cactuses.


Golovach, P., Kratsch, D., Stewart, A., & Paulusma, D. (2018). Finding cactus roots in polynomial time. Theory of Computing Systems, 62(6), 1409-1426.

Journal Article Type Article
Acceptance Date Nov 7, 2017
Online Publication Date Nov 21, 2017
Publication Date Aug 1, 2018
Deposit Date Nov 15, 2017
Publicly Available Date Nov 15, 2017
Journal Theory of Computing Systems
Print ISSN 1432-4350
Electronic ISSN 1433-0490
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 62
Issue 6
Pages 1409-1426


Accepted Journal Article (363 Kb)

Publisher Licence URL

Copyright Statement
© The Author(s) 2017 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

You might also like

Downloadable Citations