Large-girth roots of graphs

We study the problem of recognizing graph powers and computing roots of graphs. Our focus is on classes of graphs with no short cycles. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r vertical bar 3, thus improving a recently conjectured bound. Our algorithm also finds all r-th roots of a given graph that have girth at least 2r + 3 and no degree one vertices, which is a step toward a recent conjecture of Levenshtein [Discrete Math., 308 (2008), pp. 993-998] that such roots should be unique. Similar algorithms have so far been designed only for r = 2, 3. On the negative side, we prove that recognition of graph powers becomes an NP-complete problem when the bound on girth is about twice smaller