-2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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