Finding Cactus Roots in Polynomial Time

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 [Formula: see text] is called the [Formula: see text] -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 [Formula: see text] -Square Root is polynomial-time solvable when [Formula: see text] is the class of cactuses.