<p>There are several possible ways to answer this question. On the one hand, it is often assumed in distributed computing that the nodes have unbounded local computational power, because this point of view makes it possible to focus on the inherent difficulties of the distributed aspects. In such cases, lower bounds related to classical (i.e. sequential) complexity do not apply, so long as a node can collect the information of the entire graph locally (which may not be the case, though, e.g. in anonymous networks with certain symmetries). </p>

<p>But your question probably refers to a different aspect, namely whether the fact that the nodes are many does help in solving a hard problem (without unbounded local computational power). The answer is clearly no, because a distributed algorithm could be simulated by a sequential algorithm at the cost of a polynomial factor in the number of vertices.</p>

CC BY-SA 4.0
2020-02-03T08:25:03.227Z
2020-02-05T10:57:56.990Z
2020-02-05T10:57:56.990Z
Arnaud Casteigts
<p>If a certain graph problem in the <span class="math-container">$\textbf{sequential}$</span> setting is proven to have "no" better constant-factor approximation algorithm than say a 2-approx. algorithm in polynomial time, then does this also apply in the <span class="math-container">$\textbf{distributed}$</span> setting as an implication?
Thanks</p>

<graph-algorithms><approximation-algorithms><dc.distributed-comp><polynomial-time>
Sequential vs Distributed algo question
Rose
# Sequential vs Distributed algo question

(Asked by: username_0 on 2020-02-02)

If a certain graph problem in the $\textbf{sequential}$ setting is proven to have "no" better constant-factor approximation algorithm than say a 2-approx. algorithm in polynomial time, then does this also apply in the $\textbf{distributed}$ setting as an implication?
Thanks

**Tags:** graph-algorithms, approximation-algorithms, dc.distributed-comp, polynomial-time

---

## 1 answers

### Answer by username_1 on 2020-02-03. Score: 2 | Accepted answer

There are several possible ways to answer this question. On the one hand, it is often assumed in distributed computing that the nodes have unbounded local computational power, because this point of view makes it possible to focus on the inherent difficulties of the distributed aspects. In such cases, lower bounds related to classical (i.e. sequential) complexity do not apply, so long as a node can collect the information of the entire graph locally (which may not be the case, though, e.g. in anonymous networks with certain symmetries).

But your question probably refers to a different aspect, namely whether the fact that the nodes are many does help in solving a hard problem (without unbounded local computational power). The answer is clearly no, because a distributed algorithm could be simulated by a sequential algorithm at the cost of a polynomial factor in the number of vertices.


---

