Running an algorithm on the squared graph $G^2$

Question

In the context of computing (in the $\text{LOCAL}$ model of computation) I read somewhere the notion of simulating an edge in two steps.

Assume that the running time of some algorithm on a graph $G$ is $T$. Then I read that the running time of running the same algorithm on $G^2$ (the squared graph of $G$) is $2T$ since each edge can be simulated in two steps

I have a hard time understanding how this simulating an edge is to be interpreted.

Any hint is appreciated.

EDIT:

The local model is a distributed model of computation assuming:

1. Nodes of the network are assigned unique IDs of size $O(\log n)$
2. Nodes can send messages of unbounded size to their neighbors
3. Nodes can only communicate with their neighbors

(Along with the other usual assumptions of the distributed model). Reference: https://en.wikipedia.org/wiki/Distributed_computing#Models a

Answer 1

If you can only send messages in $G$, then you can simulate sending messages in $G^2$ as follows. Say that $u$ has a neighbor $w$ in $G^2$; this means $u$ and $w$ have a common neighbor in $G$. Then $u$ sends a message to $v$ with the contents "Pass the following on to $w$: ..." This requires a total of two messages to be sent.

So the specific claim we're proving is this. Suppose we have a function $f(G)$ that we want to compute, and a distributed algorithm living on a network the shape of $G$ can compute $f(G)$ in $T(G)$ steps. In that case:

• A network that actually has the shape of $G^2$ can compute $f(G^2)$ in $T(G^2)$ steps.
• A network that only has the shape of $G$ but simulates sending messages in $G^2$ can still compute $f(G^2)$, but it will take $2T(G^2)$ steps.

Some caveats, which your model of computation might or might not care about:

1. This reduction only works if $u$ knows that $w$ is its neighbor in $G^2$, and that $w$ can be reached via $v$. We can achieve this by a discovery phase at the beginning: assuming that each vertex starts out with a knowledge of the IDs of all its neighbors, each vertex sends every neighbor a message saying "Here are the IDs of all my neighbors." This adds some unavoidable term to the total time.
2. In distributed computation, the total number of messages sent might not be the most important parameter to track: maybe we should track the maximum number of messages each vertex has to deal with? Unfortunately, this can increase by more than a factor of $2$. Suppose that $G$ is a star graph: one central vertex $v$ with $n-1$ neighbors. Then $G^2$ is a complete graph. If an algorithm requires each vertex to send a message to each neighbor, then in $G^2$ no vertex needs more than $n-1$ messages. However, when $G$ is simulating $G^2$, the central vertex will also have to forward $(n-1)(n-2)$ messages, which is a quadratic increase.