We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires @math rounds in the worst case in the CONGEST model, as well as any algorithm for @math -coloring a graph, where @math is the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple @math lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a complexity of @math . We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.
Observe that finding a minimum size vertex cover is equivalent to finding a maximum size independent set. However, these problems are not equivalent in an approximation-preserving way. Distributed approximations for maximum independent set has been studied in @cite_42 @cite_43 @cite_53 @cite_0 .
@cite_0 @cite_43 @cite_53 @cite_42
2166369652 2073925702 1855768119 1813487646
We study the inapproximability of Vertex Cover and Independent Set on degree @math graphs. We prove that: Vertex Cover is Unique Games-hard to approximate to within a factor @math . This exactly matches the algorithmic result of Halperin halperin02improved up to the @math term. Independent Set is Unique Games-hard to approximate to within a factor @math . This improves the @math Unique Games hardness result of Samorodnitsky and Trevisan samorodnitsky06gowers . Additionally, our result does not rely on the construction of a query efficient PCP as in samorodnitsky06gowers . We provide a new LP relaxation of the maximum vertex cover problem and a polynomial-time algorithm that finds a solution within the approximation factor 1-1 (2q@?), where q@? is the size of the smallest clique in a given clique-partition of the edge weighting of G. A vertex cover of a graph is a subset of vertices such that each edge has at least one endpoint in the subset. Determining the minimum vertex cover is a well-known NP-complete problem in a sequential setting. Several techniques, e.g., depth-first search, a local ratio theorem, and semidefinite relaxation, have given good approximation algorithms. However, some of them cannot be applied to a distributed setting, in particular self-stabilizing algorithms. Thus only a 2-approximation solution based on a self-stabilizing maximal matching has been obviously known until now. In this paper we propose a new self-stabilizing vertex cover algorithm that achieves (2–1 Δ)-approximation ratio, where Δ is the maximum degree of a given network. We first introduce a sequential (2–1 Δ)-approximation algorithm that uses a maximal matching with the high-degree-first order of vertices. Then we present a self-stabilizing algorithm based on the same idea, and show that the output of the algorithm is the same as that of the sequential one. We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.