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 \(\mathcal {H}\) is called the \(\mathcal {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 \(\mathcal {H}\)-Square Root is polynomial-time solvable when \(\mathcal {H}\) is the class of cactuses.