Approximate Agreement (AA) is a fundamental primitive that, even in the presence of Byzantine faults, allows honest parties to obtain close (but not necessarily identical) outputs that lie within the range of their inputs. While the optimal round complexity of synchronous AA on real values is well understood, its extension to other input spaces has remained open, with fundamental questions regarding achievable resilience and round efficiency still unresolved.

The distributed coloring problem is arguably one of the key problems studied in the area of distributed graph algorithms. The most standard variant of the problem asks for a proper vertex coloring of a graph with Δ+1 colors, where Δ is the maximum degree of the graph. Despite an immense amount of work on distributed coloring problems in the distributed setting, determining the deterministic complexity of (Δ+1)-coloring in the standard message passing model remains one of the most important open questions of the area. In the LOCAL model, it is known that (Δ+1)-coloring requires Ω(log^* n) rounds even in paths and rings (i.e., when Δ = 2). For general graphs, the problem is known to be solvable in Õ(log^{5/3}n) rounds and in O(√{ΔlogΔ} + log^* n) rounds when expressing the complexity as a function of Δ and with an optimal dependency on n. In the present paper, we aim to improve our understanding of the deterministic complexity of (Δ+1)-coloring as a function of Δ in a special family of graphs for which significantly faster algorithms are already known. The neighborhood independence θ of a graph is the maximum number of pairwise non-adjacent neighbors of some node of the graph. Notable examples of graphs of bounded neighborhood independence are line graphs of graphs and bounded-rank hypergraphs. It is known that the (2Δ-1)-edge coloring problem and therefore the (Δ+1)-coloring problem in line graphs of graphs can be solved in O(log^{12}Δ+log^* n) rounds. In general, in graphs of neighborhood independence θ = O(1), it is known that (Δ+1)-coloring can be solved in 2^{O(√{logΔ})}+O(log^* n) rounds. In the present paper, we significantly improve the latter result, and we show that in graphs of neighborhood independence θ, a (Δ+1)-coloring can be computed in (θ⋅logΔ)^{O(log logΔ / log log logΔ)}+O(log^* n) rounds and thus in quasipolylogarithmic time in Δ as long as θ is at most polylogarithmic in Δ. Our algorithm can be seen as a generalization of an existing similar, but slightly weaker result for (2Δ-1)-edge coloring. We also show that the approach that leads to this polylogarithmic in Δ algorithm for (2Δ-1)-edge coloring already fails for edge colorings of hypergraphs of rank at least 3. At the core of the fast edge coloring algorithm is an algorithm to divide the edges of a graph into two parts so that up to a multiplicative error of 1+o(1), the maximum degree of the line graph induced by each part is at most half the maximum degree of the original line graph. We show that computing such a bipartition of the edges of the line graph of a hypergraph of rank at least 3 requires time logarithmic in n.

Approximate Agreement (AA) is a key consensus primitive that allows honest parties to achieve close but not necessarily identical outputs, even in the presence of Byzantine faults. While optimal round complexity for synchronous AA on real values is well understood, its extension to other input spaces remains an open problem.

In this paper, we give list coloring variants of simple iterative defective coloring algorithms. Formally, in a list defective coloring instance, each node υ of a graph is given a list Lυ of colors and a list of allowed defects dυ(x) for the colors. Each node υ needs to be colored with a color x ∈ Lυ such that at most dυ(x) neighbors (or outneighbors) of υ also pick the same color x.

The distributed coloring problem is at the core of the area of distributed graph algorithms and it is a problem that has recently seen remarkable progress. Much of the progress on deterministic algorithms is based on two main tools: a) defective colorings in which every node can have a limited number of neighbors of the same color and b) list coloring, a natural generalization of standard coloring that naturally appears when one has to extend a previously computed partial coloring to a full coloring.

We provide CONGEST model algorithms for approximating minimum weighted vertex cover and the maximum weighted matching. For bipartite graphs, we show that a $(1+\varepsilon)$-approximate weighted vertex cover can be computed deterministically in polylogarithmic time. This generalizes a corresponding result for the unweighted vertex cover problem shown in [Faour, Kuhn; OPODIS '20]. Moreover, we show that in general weighted graph families that are closed under taking subgraphs and in which we can compute an independent set of weight at least a $λ$-fraction of the total weight, one can compute a $(2-2λ+\varepsilon)$-approximate weighted vertex cover in polylogarithmic time in the CONGEST model. Our result in particular implies that in graphs of arboricity $a$, one can compute a $(2-1/a+\varepsilon)$-approximate weighted vertex cover. For maximum weighted matchings, we show that a $(1-\varepsilon)$-approximate solution can be computed deterministically in polylogarithmic CONGEST rounds (for constant $\varepsilon$). We also provide a more efficient randomized algorithm. Our algorithm generalizes results of [Lotker, Patt-Shamir, Pettie; SPAA '08] and [Bar-Yehuda, Hillel, Ghaffari, Schwartzman; PODC '17] for the unweighted case. Finally, we show that even in the LOCAL model and in bipartite graphs of degree $\leq 3$, if $\varepsilon<\varepsilon_0$ for some constant $\varepsilon_0>0$, then computing a $(1+\varepsilon)$-approximation for the unweighted minimum vertex cover problem requires $Ω\big(\frac{\log n}{\varepsilon}\big)$ rounds. This generalizes aresult of [Göös, Suomela; DISC '12], who showed that computing a $(1+\varepsilon_0)$-approximation in such graphs requires $Ω(\log n)$ rounds.