COMPUTING ROOTS OF GRAPHS IS HARD

The square of an undirected graph G is the graph G(2) On the same vert ex set such that there is an edge between two vertices in G(2) if and only if they are at distance at most 2 in G. The kth power of a graph is defined analogously. It has been conjectured that the problem of co mputing any square root of a square graph, or even that of deciding wh ether a graph is a square, is NP-hard. We settle this conjecture in th e affirmative.