Finding cactus roots in polynomial time

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

Abstract

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.

Citation

Golovach, P., Kratsch, D., Stewart, A., & Paulusma, D. (2018). Finding cactus roots in polynomial time. Theory of Computing Systems, 62(6), 1409-1426. https://doi.org/10.1007/s00224-017-9825-2

• 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
• DOI: https://doi.org/10.1007/s00224-017-9825-2