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. 

Themonotone minimal perfect hash function(MMPHF)problem is the following indexing problem. Given a set\(S=\{s_{1},\ldots,s_{n}\}\)of\(n\)distinct keys from a universe\(U\)of size\(u\), create a data structure\(\mathbf{D}\)that answers the following query:\(\rm{{R\small{ANK}}}(q)=\begin{cases}\text{rank of }q\text{ in }S&q\in S \\ \text{arbitrary answer}&\text{otherwise.}\end{cases}\) Solutions to the MMPHF problem are in widespread use in both theory and practice. The best upper bound known for the problem encodes\(\mathbf{D}\)in\(O(n\log\log\log u)\)bits and performs queries in\(O(\log u)\)time. It has been an open problem to either improve the space upper bound or to show that this somewhat odd looking bound is tight. In this article, we show the latter: any data structure (deterministic or randomized) for monotone minimal perfect hashing of any collection of\(n\)elements from a universe of size\(u\)requires\(\Omega(n\cdot\log\log\log{u})\)expected bits to answer every query correctly. We achieve our lower bound by defining a graph\(\mathbf{G}\)where the nodes are the possible\({u\choose n}\)inputs and where two nodes are adjacent if they cannot share the same\(\mathbf{D}\). The size of\(\mathbf{D}\)is then lower bounded by the log of the chromatic number of\(\mathbf{G}\). Finally, we show that the fractional chromatic number (and hence the chromatic number) of\(\mathbf{G}\)is lower bounded by\(2^{\Omega(n\log\log\log u)}\). 

Wait! What does an article on 'multi-pass graph streaming' has anything to do with a column for 'distributed computing'? 

The following question arises naturally in the study of graph streaming algorithms: Is there any graph problem which is "not too hard", in that it can be solved efficiently with total communication (nearly) linear in the number n of vertices, and for which, nonetheless, any streaming algorithm with Õ(n) space (i.e., a semi-streaming algorithm) needs a polynomial n^Ω(1) number of passes? Assadi, Chen, and Khanna [STOC 2019] were the first to prove that this is indeed the case. However, the lower bounds that they obtained are for rather non-standard graph problems. Our first main contribution is to present the first polynomial-pass lower bounds for natural "not too hard" graph problems studied previously in the streaming model: k-cores and degeneracy. We devise a novel communication protocol for both problems with near-linear communication, thus showing that k-cores and degeneracy are natural examples of "not too hard" problems. Indeed, previous work have developed single-pass semi-streaming algorithms for approximating these problems. In contrast, we prove that any semi-streaming algorithm for exactly solving these problems requires (almost) Ω(n^{1/3}) passes. The lower bound follows by a reduction from a generalization of the hidden pointer chasing (HPC) problem of Assadi, Chen, and Khanna, which is also the basis of their earlier semi-streaming lower bounds. Our second main contribution is improved round-communication lower bounds for the underlying communication problems at the basis of these reductions: - We improve the previous lower bound of Assadi, Chen, and Khanna for HPC to achieve optimal bounds for this problem. - We further observe that all current reductions from HPC can also work with a generalized version of this problem that we call MultiHPC, and prove an even stronger and optimal lower bound for this generalization. These two results collectively allow us to improve the resulting pass lower bounds for semi-streaming algorithms by a polynomial factor, namely, from n^{1/5} to n^{1/3} passes. 

Every graph with maximum degree $$\Delta$$ can be colored with $$(\Delta+1)$$colors using a simple greedy algorithm. Remarkably, recent work has shown thatone can find such a coloring even in the semi-streaming model. But, in reality,one almost never needs $$(\Delta+1)$$ colors to properly color a graph. Indeed,the celebrated \Brooks' theorem states that every (connected) graph besidecliques and odd cycles can be colored with $$\Delta$$ colors. Can we find a$$\Delta$$-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomizedsemi-streaming algorithm that given any graph, with high probability, eithercorrectly declares that the graph is not $$\Delta$$-colorable or outputs a$$\Delta$$-coloring of the graph. The proof of this result starts with a detour. We first (provably) identifythe extent to which the previous approaches for streaming coloring fail for$$\Delta$$-coloring: for instance, all these approaches can handle streams withrepeated edges and they can run in $o(n^2)$ time -- we prove that neither ofthese tasks is possible for $$\Delta$$-coloring. These impossibility resultshowever pinpoint exactly what is missing from prior approaches when it comes to$$\Delta$$-coloring. We then build on these insights to design a semi-streaming algorithm thatuses $(i)$ a novel sparse-recovery approach based on sparse-densedecompositions to (partially) recover the problematic subgraphs of the input-- the ones that form the basis of our impossibility results -- and $(ii)$ anew coloring approach for these subgraphs that allows for recoloring of othervertices in a controlled way without relying on local explorations or findingaugmenting paths that are generally impossible for semi-streaming algorithms.We believe both these techniques can be of independent interest.