Search for: All records

Vizing’s theorem states that anyn-vertexm-edge graph of maximum degreeΔcan beedge coloredusing at mostΔ+ 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found inO(mn) time. This was subsequently improved to\(\tilde{O}(m\sqrt {n}) \)time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to\(\tilde{O}(n^2) \)by [Assadi, 2024] and\(\tilde{O}(mn^{1/3}) \)by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to\(\tilde{O}(mn^{1/4}) \)by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+ 1)-edge coloring in near-linear time—in fact, onlyO(mlog Δ) time—with high probability,giving a near-optimal algorithm for this fundamental problem. 

We present dynamic algorithms withpolylogarithmicupdate time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratiostrictly better than 2. Specifically, we obtain a\(1+\frac{1}{\sqrt {2}}+\epsilon \approx 1.707+\epsilon \)approximation in bipartite graphs and a 1.973 + ϵ approximation in general graphs. We thus answer in the affirmative the value version of the major open question repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms’ approximation and worst-case update time bounds both hold w.h.p. against adaptive adversaries. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS’21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.