0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ That's false as a general statement. Can you be more specific about... well, everything? The model of computation (in more than five capital letters), the algorithm, the source of this statement. $\endgroup$ Jun 22 at 19:40
  • $\begingroup$ I added some more context about the computational model $\endgroup$
    – Alex5207
    Jun 23 at 4:07

1 Answer 1

0
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.