The theme of this paper is designing algorithms and proving hardness results for graph problems
in the following setting: we are given a graph \(G\)  and we are required to solve the problem
on the square \(G^2\) .
Computing on the square \(G^2\)  of a communication network \(G\)  is a crucial primitive in distributed applications, a prime example being the computation of a network decomposition of \(G^2\)  to obtain derandomization results [1]}. Another example is the problem of coloring \(G^2\) , which arises in frequency assignment in radio networks [2]}, [3]}.
