Square-Root Finding Problem In Graphs, A Complete Dichotomy Theorem

Babak Farzad, Majid Karimi

Graph G is the square of graph H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Given H it is easy to compute its square H^2. Determinin…