We present an efficient algorithm for the min-max correlation clustering problem. The input is a complete graph where edges are labeled as either positive (+) or negative (-), and the objective is to find a clustering that minimizes the 𝓁_∞-norm of the disagreement vector over all vertices. We address this problem with an efficient (3 + ε)-approximation algorithm that runs in nearly linear time, Õ(|E^+|), where |E^+| denotes the number of positive edges. This improves upon the previous best-known approximation guarantee of 4 by Heidrich, Irmai, and Andres [Heidrich et al., 2024], whose algorithm runs in O(|V|² + |V| D²) time, where |V| is the number of nodes and D is the maximum degree in the graph (V,E^+). Furthermore, we extend our algorithm to the massively parallel computation (MPC) model and the semi-streaming model. In the MPC model, our algorithm runs on machines with memory sublinear in the number of nodes and takes O(1) rounds. In the streaming model, our algorithm requires only Õ(|V|) space, where |V| is the number of vertices in the graph. Our algorithms are purely combinatorial. They are based on a novel structural observation about the optimal min-max instance, which enables the construction of a (3 + ε)-approximation algorithm using O(|E^+|) neighborhood similarity queries. By leveraging random projection, we further show these queries can be computed in nearly linear time.

This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework that reduces negative-weight SSSP in all these setting to $n^{o(1)}$ calls to any SSSP algorithm that works with a virtual source. More specifically, for a graph with $m$ edges, $n$ vertices, undirected hop-diameter $D$, and polynomially bounded integer edge weights, we show randomized algorithms for negative-weight SSSP with (i) $W_{SSSP}(m,n)n^{o(1)}$ work and $S_{SSSP}(m,n)n^{o(1)}$ span, given access to an SSSP algorithm with $W_{SSSP}(m,n)$ work and $S_{SSSP}(m,n)$ span in the parallel model, (ii) $T_{SSSP}(n,D)n^{o(1)}$, given access to an SSSP algorithm that takes $T_{SSSP}(n,D)$ rounds in $\mathsf{CONGEST}$, (iii) $Q_{SSSP}(m,n)n^{o(1)}$ quantum edge queries, given access to a non-negative-weight SSSP algorithm that takes $Q_{SSSP}(m,n)$ queries in the quantum edge query model. This work builds off the recent result of [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], which gives a near-linear time algorithm for negative-weight SSSP in the sequential setting. Using current state-of-the-art SSSP algorithms yields randomized algorithms for negative-weight SSSP with (i) $m^{1+o(1)}$ work and $n^{1/2+o(1)}$ span in the parallel model, (ii) $(n^{2/5}D^{2/5} + \sqrt{n} + D)n^{o(1)}$ rounds in $\mathsf{CONGEST}$, (iii) $m^{1/2}n^{1/2+o(1)}$ quantum queries to the adjacency list or $n^{1.5+o(1)}$ quantum queries to the adjacency matrix. Our main technical contribution is an efficient reduction for computing a low-diameter decomposition (LDD) of directed graphs to computations of SSSP with a virtual source. Efficiently computing an LDD has heretofore only been known for undirected graphs in both the parallel and distributed models.

We consider the expander routing problem formulated by Ghaffari, Kuhn, and Su (PODC 2017), where the goal is to route all the tokens to their destinations given that each vertex is the source and the destination of at most deg(υ) tokens. They developed randomized algorithms that solve this problem in poly [EQUATION] rounds in the CONGEST model, where ϕ is the conductance of the graph. In addition, as noted by Chang, Pettie, Saranurak, and Zhang (JACM 2021), it is possible to obtain a preprocessing/query tradeoff so that the routing queries can be answered faster at the cost of more preprocessing time. The efficiency and flexibility of the processing/query tradeoff of expander routing have led to many other distributed algorithms in the CONGEST model, such as subpolynomial-round minimum spanning tree algorithms in expander graphs and near-optimal algorithms for k-clique enumeration in general graphs.

In this paper, we study parallel algorithms for the correlation clustering problem, where every pair of two different entities is labeled with similar or dissimilar. The goal is to partition the entities into clusters to minimize the number of disagreements with the labels. Currently, all efficient parallel algorithms have an approximation ratio of at least 3. In comparison with the 1.994 + ɛ ratio achieved by polynomial-time sequential algorithms [25], a significant gap exists.

The maximum weighted matching (mwm) problem is one of the most well-studied combinatorial optimization problems in distributed graph algorithms. Despite a long development on the problem, and the recent progress of Fischer, Mitrovic, and Uitto [16] who gave a poly(1/ϵ, log n)-round algorithm for obtaining a (1 − ϵ)-approximate solution for unweighted maximum matching, it had been an open problem whether a (1 − ϵ)-approximate mwm can be obtained in poly(1/ϵ, log n) rounds in the CONGEST model. Algorithms with such running times were only known for special graph classes such as bipartite graphs [1] and minor-free graphs [8]. For general graphs, the previously known algorithms require exponential in (1/ϵ) rounds for obtaining a (1 − ϵ)-approximate solution [13] or achieve an approximation factor of at most 2/3 [1]. In this work, we settle this open problem by giving a deterministic poly(1/ϵ, log n)-round algorithm for computing a (1 − ϵ)-approximate mwm for general graphs in the CONGEST model. Our proposed solution extends the algorithm of Fischer, Mitrovic, and Uitto [16], blends in the sequential algorithm from Duan and Pettie [11] and the work of Faour, Fuchs, and Kuhn [13]. Interestingly, this solution also implies a CREW PRAM algorithm with poly(1/ϵ, log n) span using only O(m) processors, and a poly(1/ϵ)-passes algorithm in the semi-streaming model.

The paper presents parallel algorithms for multiplying implicit simple unit-Monge matrices (Krusche and Tiskin, PPAM 2009) of size n x n in the EREW PRAM model. We show implicit simple unit-Monge matrices multiplication of size n x n can be achieved by a deterministic EREW PRAM algorithm with O(n log n log log n) total work and O(log3 n) span. This implies that there is a deterministic EREW PRAM algorithm solving the longest increasing subsequence (LIS) problem in O(n log2 n log log n) work and O(log 4 n) span. Furthermore, with randomization and bitwise operations, implicitly multiplying two simple unit-Monge matrices can be improved to O(n log n) work and O(log3n) span, which leads to a randomized EREW PRAM algorithm obtaining LIS in O(nlog2n) work and O(log4n) span with high probability. In the regime where the LIS has length k = Ψ(log3n), our results improve the span from Õ(n2/3) (Krusche and Tiskin, SPAA 2010) and O(klog n) (Gu, Men, Shen, Sun, and Wan, SPAA 2023) to O(log4 n) while the total work remains near optimal Õ (n).

Abstract. Given a graph [Formula: see text] with arboricity [Formula: see text], we study the problem of decomposing the edges of [Formula: see text] into [Formula: see text] disjoint forests in the distributed [Formula: see text] model. Here [Formula: see text] may be a simple graph or multigraph. While there is a polynomial time centralized algorithm for [Formula: see text]-forest decomposition (e.g., [H. Imai, J. Oper. Res. Soc. Japan, 26 (1983), pp. 186–211]), it remains an open question how close we can get to this exact decomposition in the [Formula: see text] model. Barenboim and Elkin [L. Barenboim and M. Elkin, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, Distrib. Comput., 22 (2010), pp. 363–379] developed a [Formula: see text] algorithm to compute a [Formula: see text]-forest decomposition in [Formula: see text] rounds. Ghaffari and Su [ Proc. 28 th ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 2505–2523] made further progress by computing a [Formula: see text]-forest decomposition in [Formula: see text] rounds when [Formula: see text]; i.e., the limit of their algorithm is an [Formula: see text]-forest decomposition. This algorithm, based on a combinatorial construction of Alon, McDiarmid, and Reed [ Combinatorica, 12 (1992), pp. 375–380], in fact provides a decomposition of the graph into star-forests, i.e., each forest is a collection of stars. Our main goal is to reduce the threshold of [Formula: see text] in [Formula: see text]-forest decomposition. We obtain a number of results with different parameters; some notable examples are the following: (1) An [Formula: see text]-round algorithm when [Formula: see text] in multigraphs, where [Formula: see text] is any arbitrary constant; (2) an [Formula: see text]-round algorithm when [Formula: see text] in multigraphs; (3) an [Formula: see text]-round algorithm when [Formula: see text] in multigraphs (this also covers an extension of the forest-decomposition problem to list-edge-coloring); (4) an [Formula: see text]-round algorithm for star-forest decomposition for [Formula: see text] in simple graphs (when [Formula: see text], this also covers a list-coloring variant). Our techniques also give an algorithm for [Formula: see text]-outdegree-orientation in [Formula: see text] rounds, which is the first algorithm with linear dependency on [Formula: see text]. At a high level, the first three results come from a combination of network decomposition, load balancing, and a new structural result on local augmenting sequences. The fourth result uses a more careful probabilistic analysis for the construction of Alon, McDiarmid, and Reed; the bounds on star-forest decomposition were not previously known even non constructively.

Miller and Reif’s FOCS'85 [Gary L. Miller and John H. Reif, 1989] classic and fundamental tree contraction algorithm is a broadly applicable technique for the parallel solution of a large number of tree problems. Additionally it is also used as an algorithmic design technique for a large number of parallel graph algorithms. In all previously explored models of computation, however, tree contractions have only been achieved in Ω(log n) rounds of parallel run time. In this work, we not only introduce a generalized tree contraction method but also show it can be computed highly efficiently in O(1/ε³) rounds in the Adaptive Massively Parallel Computing (AMPC) setting, where each machine has O(n^ε) local memory for some 0 < ε < 1. AMPC is a practical extension of Massively Parallel Computing (MPC) which utilizes distributed hash tables [MohammadHossein Bateni et al., 2017; Behnezhad et al., 2019; Raimondas Kiveris et al., 2014]. In general, MPC is an abstract model for MapReduce, Hadoop, Spark, and Flume which are currently widely used across industry and has been studied extensively in the theory community in recent years. Last but not least, we show that our results extend to multiple problems on trees, including but not limited to maximum and maximal matching, maximum and maximal independent set, tree isomorphism testing, and more.

Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within (1 ± ε) factors in poly(log n, 1/ε) rounds in the LOCAL model via network decompositions [Ghaffari, Kuhn, and Maus, STOC 2018]. These approaches, however, require sending messages of unlimited size, so they do not extend to the more realistic CONGEST model, which restricts the message size to be O(log n) bits. For example, despite the long line of research devoted to the distributed matching problem, it still remains a major open problem whether an (1-ε)-approximate maximum weighted matching can be computed in poly(log n, 1/ε) rounds in the CONGEST model.

Given a graph G=(V,E) with arboricity a, we study the problem of decomposing the edges of G into (1+ε)a disjoint forests in the distributed LOCAL model. While there is a polynomial time centralized algorithm for a-forest decomposition (e.g. [Imai, J. Operation Research Soc. of Japan '83]), it remains an open question how close we can get to this exact decomposition in the LOCAL model.

We study the problem of distributed task allocation in multi-agent systems. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the number of agents required to perform each task. The goal of the agents is to cooperatively allocate themselves to the tasks to satisfy the demand vector. We study the dynamic version of the problem where the demand vector changes over time. Here, the goal is to minimize the switching cost, which is the number of agents that change tasks in response to a change in the demand vector. The switching cost is an important metric since changing tasks may incur significant overhead. We study a mathematical formalization of the above problem introduced by Su, Su, Dornhaus, and Lynch, which can be reformulated as a question of finding a low distortion embedding from symmetric difference to Hamming distance. In this model it is trivial to prove that the switching cost is at least 2. We present the first non-trivial lower bounds for the switching cost, by giving lower bounds of 3 and 4 for different ranges of the parameters.

The densest subgraph problem, introduced in the 80s by Picard and Queyranne as well as Goldberg, is a classic problem in combinatorial optimization with a wide range of applications. The lowest outdegree orientation problem is known to be its dual problem. We study both the problem of finding dense subgraphs and the problem of computing a low outdegree orientation in the distributed settings. Suppose $G=(V,E)$ is the underlying network as well as the input graph. Let $D$ denote the density of the maximum density subgraph of $G$. Our main results are as follows. Given a value $\tilde{D} \leq D$ and $0 < ε< 1$, we show that a subgraph with density at least $(1-ε)\tilde{D}$ can be identified deterministically in $O((\log n) / ε)$ rounds in the LOCAL model. We also present a lower bound showing that our result for the LOCAL model is tight up to an $O(\log n)$ factor. In the CONGEST model, we show that such a subgraph can be identified in $O((\log^3 n) / ε^3)$ rounds with high probability. Our techniques also lead to an $O(diameter + (\log^4 n)/ε^4)$-round algorithm that yields a $1-ε$ approximation to the densest subgraph. This improves upon the previous $O(diameter /ε\cdot \log n)$-round algorithm by Das Sarma et al. [DISC 2012] that only yields a $1/2-ε$ approximation. Given an integer $\tilde{D} \geq D$ and $Ω(1/\tilde{D}) < ε< 1/4$, we give a deterministic, $\tilde{O}((\log^2 n) /ε^2)$-round algorithm in the CONGEST model that computes an orientation where the outdegree of every vertex is upper bounded by $(1+ε)\tilde{D}$. Previously, the best deterministic algorithm and randomized algorithm by Harris [FOCS 2019] run in $\tilde{O}((\log^6 n)/ ε^4)$ rounds and $\tilde{O}((\log^3 n) /ε^3)$ rounds respectively and only work in the LOCAL model.

Vizing showed that it suffices to color the edges of a simple graph using Δ + 1 colors, where Δ is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithm is known for obtaining such coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Δ + Θ(√Δ))-edge-coloring algorithm that runs in (n) rounds by Chang et al. [SODA 2018] and the deterministic (Δ + (n))-edge-coloring algorithm that runs in (Δ, logn) rounds by Ghaffari et al. [STOC 2018].

We study distributed algorithms for some fundamental problems in data summarization. Given a communication graph $G$ of $n$ nodes each of which may hold a value initially, we focus on computing $\sum_{i=1}^N g(f_i)$, where $f_i$ is the number of occurrences of value $i$ and $g$ is some fixed function. This includes important statistics such as the number of distinct elements, frequency moments, and the empirical entropy of the data. In the CONGEST model, a simple adaptation from streaming lower bounds shows that it requires $\tildeΩ(D+ n)$ rounds, where $D$ is the diameter of the graph, to compute some of these statistics exactly. However, these lower bounds do not hold for graphs that are well-connected. We give an algorithm that computes $\sum_{i=1}^{N} g(f_i)$ exactly in $τ_G \cdot 2^{O(\sqrt{\log n})}$ rounds where $τ_G$ is the mixing time of $G$. This also has applications in computing the top $k$ most frequent elements. We demonstrate that there is a high similarity between the GOSSIP model and the CONGEST model in well-connected graphs. In particular, we show that each round of the GOSSIP model can be simulated almost-perfectly in $\tilde{O}(τ_G $ rounds of the CONGEST model. To this end, we develop a new algorithm for the GOSSIP model that $1\pm ε$ approximates the $p$-th frequency moment $F_p = \sum_{i=1}^N f_i^p$ in $\tilde{O}(ε^{-2} n^{1-k/p})$ rounds, for $p \geq2$, when the number of distinct elements $F_0$ is at most $O\left(n^{1/(k-1)}\right)$. This result can be translated back to the CONGEST model with a factor $\tilde{O}(τ_G)$ blow-up in the number of rounds.

This paper gives drastically faster gossip algorithms to compute exact and approximate quantiles.

(Delta+1)-vertex coloring is one of the most fundamental symmetry breaking graph problems, receiving tremendous amount of attention over the last decades. We consider the congested clique model where in each round, every pair of vertices can exchange O(log n) bits of information. In a recent breakthrough, Yi-Jun Chang, Wenzheng Li, and Seth Pettie [CLP-STOC'18] presented a randomized (Delta+1)-list coloring algorithm in the LOCAL model that works in O(log^*n+Det_{deg}(log log n)) rounds, where Det_{deg}(n') is the deterministic LOCAL complexity of (deg+1)-list coloring algorithm on n'-vertex graphs. Unfortunately, the CLP algorithm uses large messages and hence cannot be efficiently implemented in the congested clique model when the maximum degree Delta is large (in particular, when Delta=omega(sqrt{n})). Merav Parter [P-ICALP'18] recently provided a randomized (Delta+1)-coloring algorithm in O(log log Delta * log^* Delta) congested clique rounds based on a careful partitioning of the input graph into almost-independent subgraphs with maximum degree sqrt{n}. In this work, we significantly improve upon this result and present a randomized (Delta+1)-coloring algorithm with O(log^* Delta) rounds, with high probability. At the heart of our algorithm is an adaptation of the CLP algorithm for coloring a subgraph with o(n) vertices and maximum degree Omega(n^{5/8}) in O(log^* Delta) rounds. The approach is built upon a combination of techniques, this includes: the graph sparsification of [Parter-ICALP'18], and a palette sampling technique adopted to the CLP framework.

We give a new randomized distributed algorithm for (Δ +1)-coloring in the LOCAL model, running in O (√ log Δ)+ 2 O (√log log n ) rounds in a graph of maximum degree Δ. This implies that the (Δ +1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds of Ω(min(√/log n log log n , /log Δ log log Δ)) by Kuhn, Moscibroda, and Wattenhofer [PODC’04]. Our algorithm also extends to list-coloring where the palette of each node contains Δ +1 colors. We extend the set of distributed symmetry-breaking techniques by performing a decomposition of graphs into dense and sparse parts.

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in O ( m √ n log( nN )) time, O ( m √ n ) per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs [16, 20, 36, 37]. Here, m , n , and N bound the number of edges, vertices, and magnitude, respectively, of any integer edge weight. Our result improves on a 25-year-old algorithm of Gabow and Tarjan, which runs in O ( m √ n log n α ( m , n ) log( nN )) time.

We present a randomized distributed algorithm that computes a minimum spanning tree in τ(G) · 2O(√(log n log log n))) rounds, in any n-node graph G with mixing time τ(G). This result provides a sub-polynomial complexity for a wide range of graphs of practical interest, and goes below the celebrated Ω(D+ √n) lower bound of Das Sarma et al. [STOC'11] which holds for some worst-case general graphs. The core novelty in this result is a distributed method for permutation routing. In this problem, one is given a number of source-destination pairs, and we should deliver one packet from each source to its destination, all in parallel, in the shortest span of time possible. Our algorithm allows us to route and deliver all these packets in τ(G) · 2O(√(log n log log n)) rounds, assuming that each node v is the source or destination for at most dG(v) packets. The main technical ingredient in this routing result is a certain hierarchical embedding of good-expansion random graphs on the base graph, which we believe can be of interest well beyond this work.

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in time, per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs [29, 18]. Here m,n, and n bound the number of edges, vertices, and magnitude of any integer edge weight. Our result improves on a 25-year old algorithm of Gabow and Tarjan, which runs in time.

We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: We present a poly log n round deterministic algorithm for (2Δ – 1)•(1+o(1))-edge-coloring, where Δ denotes the maximum degree. Modulo the 1 + o(1) factor, this settles one of the long-standing open problems of the area from the 1990's (see e.g. Panconesi and Srinivasan [PODC'92]). Indeed, a weaker requirement of (2Δ – 1) · poly log Δ-edge- coloring in poly log n rounds was asked for in the 4th open question in the Distributed Graph Coloring book by Barenboim and Elkin. We show that sinkless orientation—i.e., orienting edges such that each node has at least one outgoing edge—on Δ-regular graphs can be solved in O(logA log n) rounds randomized and in O(logA n) rounds deterministically. These prove the corresponding lower bounds by Brandt et al. [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight. Moreover, these show that sinkless orientation exhibits an exponential separation between its randomized and deterministic complexities, akin to the results of Chang et al. for Δ-coloring Δ- regular trees. We present a randomized O (log4 n) round algorithm for orienting a-arboricity graphs with maximum out-degree a(1 + ∊). This can be also turned into a decomposition into a(1 + ∊) forests when a = 0(logn) and into a(1 + ∊) pseduo-forests when a = o(log n). Obtaining an efficient distributed decomposition into less than 2a forests was stated as the 10th open problem in the book by Barenboim and Elkin.

Adaptive collective systems are common in biology and beyond. Typically, such systems require a task allocation algorithm: a mechanism or rule-set by which individuals select particular roles. Here we study the performance of such task allocation mechanisms measured in terms of the time for individuals to allocate to tasks. We ask: (1) Is task allocation fundamentally difficult, and thus costly? (2) Does the performance of task allocation mechanisms depend on the number of individuals? And (3) what other parameters may affect their efficiency? We use techniques from distributed computing theory to develop a model of a social insect colony, where workers have to be allocated to a set of tasks; however, our model is generalizable to other systems. We show, first, that the ability of workers to quickly assess demand for work in tasks they are not currently engaged in crucially affects whether task allocation is quickly achieved or not. This indicates that in social insect tasks such as thermoregulation, where temperature may provide a global and near instantaneous stimulus to measure the need for cooling, for example, it should be easy to match the number of workers to the need for work. In other tasks, such as nest repair, it may be impossible for workers not directly at the work site to know that this task needs more workers. We argue that this affects whether task allocation mechanisms are under strong selection. Second, we show that colony size does not affect task allocation performance under our assumptions. This implies that when effects of colony size are found, they are not inherent in the process of task allocation itself, but due to processes not modeled here, such as higher variation in task demand for smaller colonies, benefits of specialized workers, or constant overhead costs. Third, we show that the ratio of the number of available workers to the workload crucially affects performance. Thus, workers in excess of those needed to complete all tasks improve task allocation performance. This provides a potential explanation for the phenomenon that social insect colonies commonly contain inactive workers: these may be a 'surplus' set of workers that improves colony function by speeding up optimal allocation of workers to tasks. Overall our study shows how limitations at the individual level can affect group level outcomes, and suggests new hypotheses that can be explored empirically.

The (∆+1)-coloring problem is a fundamental symmetry breaking problem in distributed computing. We give a new randomized coloring algorithm for (∆+1)-coloring running in O(√log ∆)+ 2^O(√log log n) rounds with probability 1-1/n^Ω(1) in a graph with n nodes and maximum degree ∆. This implies that the (∆+1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Our algorithm also extends to the list-coloring problem where the palette of each node contains ∆+1 colors.

Graph coloring is a central problem in distributed computing. Both vertex- and edge-coloring problems have been extensively studied in this context. In this paper we show that a (2Δ — l)-edge-coloring can be computed in time smaller than logε n for any ε > 0, specifically, in rounds. This establishes a separation between the (2Δ — 1)-edge-coloring and Maximal Matching problems, as the latter is known to require time [15]. No such separation is currently known between the (Δ + l)-vertex-coloring and Maximal Independent Set problems. We devise a (1 + ε)Δ-edge-coloring algorithm for an arbitrarily small constant ε > 0. This result applies whenever Δ ≥ Δε, for some constant Δε which depends on e. The running time of this algorithm is . A much earlier logarithmic-time algorithm by Dubhashi, Grable and Panconesi [11] assumed Δ ≥ (log n)1+Ω(1). For Δ = (log n)1+Ω(1) the running time of our algorithm is only O (log* n). This constitutes a drastic improvement of the previous logarithmic bound [11, 9]. Our results for (2Δ — 1)-edge-coloring also follows from our more general results concerning (1 — ε)-locally sparse graphs. Specifically, we devise a (Δ + l)-vertex coloring algorithm for (1 — ε)-locally sparse graphs that runs in O(log* Δ + log(l/ε)) rounds for any ε > 0, provided that ε Δ = (log n)1+Ω(1). We conclude that the (Δ + l)-vertex coloring problem for (1 — ε)-locally sparse graphs can be solved in time. This imply our result about (2Δ — 1)-edge-coloring, because (2Δ — 1)-edge-coloring reduces to (Δ + l)-vertex-coloring of the line graph of the original graph, and because line graphs are (1/2 + o(1))-locally sparse.

The Lovasz Local Lemma (LLL), introduced by Erdos and Lovasz in 1975, is a powerful tool of the probabilistic method that allows one to prove that a set of n "bad" events do not happen with non-zero probability, provided that the events have limited dependence. However, the LLL itself does not suggest how to find a point avoiding all bad events. Since the work of Beck (1991) there has been a sustained effort to find a constructive proof (i.e. an algorithm) for the LLL or weaker versions of it. In a major breakthrough Moser and Tardos (2010) showed that a point avoiding all bad events can be found efficiently. They also proposed a distributed/parallel version of their algorithm that requires O(log2 n) rounds of communication in a distributed network.

In this paper, we study the problem of approximating the minimum cut in a distributed message-passing model, the CONGEST model. The minimum cut problem has been well-studied in the context of centralized algorithms. However, there were no known non-trivial algorithms in the distributed model until the recent work of Ghaffari and Kuhn. They gave randomized algorithms for finding cuts of size O(ε-1λ) and (2 + ε)λ in O(D) + Õ(n1/2+ε) rounds and Õ(D + √n) rounds respectively, where λ is the size of the minimum cut. This matches the lower bound they provided up to a polylogarithmic factor. Yet, no scheme that achieves (1 + ε)-approximation ratio is known. We give a distributed randomized algorithm that finds a cut of size (1 + ε)λ in Õ(D + √n) time, which is optimal up to polylogarithmic factors.

Given a weighted bipartite graph, the maximum weight matching (MWM) problem is to find a set of vertex-disjoint edges with maximum weight. We present a new scaling algorithm that runs in O(m√n log N) time, when the weights are integers within the range of [0, N]. The result improves the previous bounds of O(Nm√n) by Gabow and O(m√n log (nN)) by Gabow and Tarjan over 20 years ago. Our improvement draws ideas from a not widely known result, the primal method by Balinski and Gomory.