Faster Deterministic Streaming Vertex Coloring

We begin by reviewing the approach of [4]. Their algorithm maintains a partial coloring $\varphi :V\to [O(\mathrm{\Delta })]\cup \{\perp \}$ ($\perp$ means uncolored) of the graph $G$ and gradually extends it to reduce the number of uncolored vertices over multiple passes. Initially, it starts with an empty coloring where all vertices are uncolored. Then, they show that in every $O(1)$ passes over the input stream, one could reduce the number of uncolored vertices by a constant factor. So, in the end, the total number of passes would be $O(\log \mathrm{\Delta })$. Morally speaking, imagine that we could use randomness and in each round we draw a uniformly random color $c(v)$ from $O(\mathrm{\Delta })$ to each uncolored vertex $v\in {\varphi }^{-1}(\perp )$. Then, we can argue that for each vertex $v\in {\varphi }^{-1}(\perp )$, the probability that $c(v)$ conflicts with some neighboring $c(u)$ or $\varphi (w)$ is bounded away from $1$, or more precisely:

Then, we can extend the partial coloring $\varphi$ by assigning $c(v)$ to each uncolored vertex $v$ without any conflicts with its neighbors, which would reduce the number of uncolored vertices by a constant factor. Derandomizing this approach can be done using universal hash functions instead of independent random colors; this is because we only need to upper bound the total number of vertex conflicts, and so we can choose the hash function with the minimum number of conflicts to extend $\varphi$.

To reduce the number of passes, a natural observation is that the $v$’s conflict probability (the first term in Equation 1):

becomes smaller when the number of uncolored vertices shrinks. To see this, imagine that at the moment $|{\varphi }^{-1}(\perp )|=ϵn$ for some $ϵ\in (0,1)$. Then hopefully each vertex $v\in {\varphi }^{-1}(\perp )$ has only $ϵ\mathrm{\Delta }$ neighbors in vertex set ${\varphi }^{-1}(\perp )$ (proportional to the size of ${\varphi }^{-1}(\perp )$ compared to $V$). If we could draw a uniformly random color for each $v\in {\varphi }^{-1}(\perp )$ from all $v$’s available colors $[O(\mathrm{\Delta })]\setminus \{\varphi (u)\mid u\in N(v)\}$, then we could completely avoid the second conflict probability term in Equation 1:

and then the conflict probability of $v$ would be at most:

So, under a random color extension (which always draws available colors) to $\varphi$, in expectation a proportion of $1-\mathrm{\Omega }(ϵ)$ would be colored, leaving $O({ϵ}^{2}n)$ uncolored vertices; in other words, the ratio $|{\varphi }^{-1}(\perp )|/n$ would drop quadratically. Therefore, the total number of passes would be at most $O(\log \log \mathrm{\Delta })$.

The main difficulty of implementing this natural attempt is that we do not have direct access to the available colors of each vertex $v\in {\varphi }^{-1}(\perp )$ which is $[O(\mathrm{\Delta })]\setminus \{\varphi (u)\mid u\in N(v)\}$; that is, those colors not yet used by any of $v$’s neighbor under color assignment $\varphi$. Instead, what we do have access to is only a data stream of unavailable colors $\{\varphi (u)\mid u\in N(v)\}$ for each $v\in {\varphi }^{-1}(\perp )$ converted from the input graph stream. This task of accessing available colors given a data stream of unavailable colors can be viewed as a missing item problem. In the standard formulation of the missing item problem, the algorithm is given a stream of integers $x_1,x_2,\mathrm{\dots }{x}_N\in [M]$, and the goal is usually to find some or (approximately) count all elements in $[M]\setminus \{x_1,x_2,\mathrm{\dots },x_N\}$. This problem was studied in [29] and the author showed a deterministic space lower bound of $\tilde{\mathrm{\Omega }}(N)$ against any streaming algorithm that outputs any single missing item. In our case, $N$ is as large as $\mathrm{\Delta }$, and so we would need to allocate $\tilde{\mathrm{\Omega }}(\mathrm{\Delta })$ space for each $v\in {\varphi }^{-1}(\perp )$ which is infeasible.

As hinted by the impossibility result from [29], it is generally hard to assume access to the set of available colors $[O(\mathrm{\Delta })]\setminus \{\varphi (u)\mid u\in N(v)\}$ and bypass the conflicts with neighbors that are already colored, which is the main source of technical difficulty, without using space of palette size $O(\mathrm{\Delta })$, per uncolored vertex $v$.

To circumvent the $O(\mathrm{\Delta })$ space requirement per uncolored vertex while still avoiding the conflicts with colored neighbors, the basic idea is to reduce the palette size. More concretely, we are going to partition the palette into much smaller sub-palettes:

and also partition the uncolored vertex set into vertex subsets:

such that it is possible to assign colors from $C_i$ to all vertices in $B_i$ in a valid manner, $\forall 1\le i\le l$. If all the sub-palettes $C_i$ are small, and the union of the induced subgraphs $G[B_i]$ fits in $\tilde{O}(n)$ bits of memory, then we can compute and store all the available colors and the subgraphs in memory over a single pass, and then complete the color extension.

This vertex and color partitioning approach has been previously adopted in some recent distributed graph coloring literature [15, 27, 28, 19, 18], in which we found [19] particularly helpful for our reference. The authors of [19] worked on the problem of computing a $(\mathrm{\Delta }+1)$-coloring in the congested clique model. Their main algorithm can deterministically compute a pair of vertex and color partitions but with an extra bad vertex subset:

such that for every vertex $v\in B_i,\forall 1\le i\le l$, the size of $C_i$ is strictly larger than the number of its neighbors in $B_i$, or more formally $\left|C_i\right|>{\mathrm{deg}}_{G[B_i]}(v)$ (note that they directly compute a full coloring in one shot after partitioning, and they do not repeatedly use color extensions like us, so they do not need to exclude any unavailable colors from sub-palette $C_i$). Here the set $B_{\text{bad}}$ will be a small vertex set of size $O(n/\mathrm{\Delta })$ collecting all the vertices that violate this inequality. In the end, they show that each induced subgraph $G[B_{\text{bad}}],G[B_i],\forall 1\le i\le l$ has size $O(n)$ which fits in the local memory of a single machine, so they could compute the whole coloring using $O(n)$ machines in $O(1)$ communication rounds.

To deterministically compute a good pair of vertex and color partitions, the authors of [19] used $O(1)$-wise independent hash families to map vertices and colors to their subsets and sub-palettes. More specifically, they build two $O(1)$-wise independent hash families ${\mathscr{H}}_1,{\mathscr{H}}_2$ where ${\mathscr{H}}_1$ contains functions $h:V\to [{\mathrm{\Delta }}^{0.9}]$ and ${\mathscr{H}}_2$ contains functions $h:[\mathrm{\Delta }+1]\to [{\mathrm{\Delta }}^{0.9}]$; in reality, the exponent of range is a much smaller constant (say, $0.1$ instead of $0.9$), and the actual algorithm needs to repeat the partitions for $O(1)$ times [19]. Then, they used the method of conditional expectation to find a good pair of hash functions $(h_1^{\ast },h_2^{\ast })\in {\mathscr{H}}_1\times {\mathscr{H}}_2$ which is used as their vertex and color partitions.

It turns out that in our streaming setting, as opposed to the congested clique setting, it is rather prohibitive to find a good hash function out of an $O(1)$-wise independent hash family. According to standard literature [26, 1, 17], ${\mathscr{H}}_1,{\mathscr{H}}_2$ have sizes polynomial in terms of their domains which are $n^{O(1)},{\mathrm{\Delta }}^{O(1)}$, respectively. To decide if a hash function pair $(h_1,h_2)\in {\mathscr{H}}_1\times {\mathscr{H}}_2$ induces a good partition for any specific vertex $v\in {\varphi }^{-1}(\perp )$, we need to count its degree in the same bin which is $\left|\{h_1(v)=h_1(u)\mid u\in N(v)\}\right|$, as well as estimate its available colors which is $\{c\mid h_2(c)=h_1(v)\}\setminus \{\varphi (u)\mid u\in N(v)\}$. This requires maintaining a counter for each pair $(h_1,h_2)$ and each vertex $v\in {\varphi }^{-1}(\perp )$ during one stream pass, and this totals a space usage of $O\left(|{\varphi }^{-1}(\perp )|\cdot \left(n^{O(1)}+{\mathrm{\Delta }}^{O(1)}\right)\right)=n^{1+O(1)}$.

In order to reduce the space, instead of relying on $O(1)$-wise independence, we will switch to almost $O(1)$-wise independence [2, 25] where the hash family only has size roughly $M^{O(1)}{\log }^{O(1)}N$ with $N,M$ being the domain and range sizes. Plugging in our setting, $N=n$ so the memory requirement would be $\tilde{O}\left(|{\varphi }^{-1}(\perp )|\cdot M^{O(1)}\right)$. Still, we cannot use the same domain size of $M={\mathrm{\Delta }}^{\mathrm{\Omega }(1)}$ as in [19]. This leads to the following modifications in algorithm parameters.

• $\mathrm{■}$

  To make $|{\varphi }^{-1}(\perp )|$ moderately small, we can run the color extension method of [4] for $\sqrt{\log \mathrm{\Delta }}$ rounds as a preprocessing step. This takes $O(\sqrt{\log \mathrm{\Delta }})$ passes over the data stream and brings down the number of uncolored vertices to $|{\varphi }^{-1}(\perp )|\le n/2^{\mathrm{\Omega }(\sqrt{\log \mathrm{\Delta }})}$.

• $\mathrm{■}$

  Set the range size of hash functions $M=2^{\mathrm{\Theta }\left(\sqrt{\log \mathrm{\Delta }}\right)}$ which keeps the total memory requirement below $\tilde{O}(n)$. Since in the end we want a color partition of small size so that we can deterministically compute all the available colors around each uncolored vertex, we will recursively partition each sub-palette for ${\log }_M\mathrm{\Delta }=O(\sqrt{\log \mathrm{\Delta }})$ rounds.

Let us focus on a single round where we are given a pair of partitions:

and our goal is to refine this partition further so that the sizes of sub-palettes $C_i$ and subgraphs $G[B_i]$ become smaller by a factor of $2^{-\mathrm{\Omega }(\sqrt{\log \mathrm{\Delta }})}$. As discussed above, we will use almost $O(1)$-wise independent hash families ${\mathscr{H}}_1,{\mathscr{H}}_2$ that map uncolored vertices and colors to the range $[M]$ for some $M=2^{\mathrm{\Omega }(\sqrt{\log \mathrm{\Delta }})}$. Each vertex $v\in B_i$ will compute some statistics during a single pass over the stream for each pair of hash functions $(h_1,h_2)\in {\mathscr{H}}_1\times {\mathscr{H}}_2$:

1. (i)

   the number of neighbors under $h_1$, namely the size of the set $\{u\mid h_1(u)=h_1(v),u\in B_i\}$;

2. (ii)

   the (approximate) number of available colors in the color set:

   $$\{c\mid h_2(c)=h_1(v),c\in C_i\}\setminus \{\varphi (u)\mid u\in N(v)\}$$

If the value of (ii) is larger than (i), then $v$ would give one vote to the pair $(h_1,h_2)$. In the end, we hope that there exists a good pair $(h_1^{\ast },h_2^{\ast })$ which receives votes from a proportion of at least $1-2^{-\mathrm{\Omega }(\sqrt{\log \mathrm{\Delta }})}$ uncolored vertices. If so, we would take this pair $(h_1^{\ast },h_2^{\ast })$ to generate a partition refinement, and all vertices which did not vote to $(h_1^{\ast },h_2^{\ast })$ would move to $B_{\text{bad}}$. After $O(\sqrt{\log \mathrm{\Delta }})$ rounds of partition refinement, we will be able to color all vertices in $B_i$’s using colors from $C_i$’s in one pass, as $C_i$’s will be small enough, leaving a very small uncolored vertex set $B_{\text{bad}}$.

Assume inductively that $v$ has more available colors in $C_i$ than its neighbors in $B_i$. To preserve this property for a refined partition, we argue that both (i)(ii) will concentrate around their expectations using concentration inequalities for almost $k$-wise independence; such concentration bounds were previously studied in [20] but in the context of cryptography with a somewhat different definition of almost $k$-wise independence from ours, we provide the full proof of our concentration bound in the full version of this paper. (See Lemma 10 for the formal statement).

By the concentration bound, we know that for most vertices $v\in B_i$, it should vote for most pairs $(h_1,h_2)$. The main difficulty arises from verifying which pairs $(h_1,h_2)$ are good. Computing (i) is straightforward, whereas computing (ii) is much more challenging because it is still a missing item problem which is hard according to [29]. The difference is that here we only need a lower bound estimation of the number of the available colors, not output any specific available color. A basic idea is to lower bound (ii) by:

The second term (which will be our main focus) $\left|\{\varphi (u)\mid u\in N(v),h_2(\varphi (u))=h_1(v),\varphi (u)\in C_i\}\right|$ counts the number of distinct colors used by $v$’s neighbors, while the set $\{u\in N(v)\mid h_2(\varphi (u))=h_1(v),\varphi (u)\in C_i\}$ is what the algorithm sees in the data stream. Ideally, if we could directly compute the number of distinct neighbor colors, then we could use Equation 3 as our lower bound which aligns well with concentration inequalities. However, this is impossible for deterministic algorithms without using $\tilde{\mathrm{\Omega }}(\mathrm{\Delta })$ space [22], and we could only use the linear estimator Equation 4 as our lower bound; this linear estimator was also used in [3] for deterministic streaming $(\mathrm{\Delta }+1)$-coloring.

Unfortunately, concentration bounds of the linear estimation

of distinct neighbor colors could be very poor. Imagine that all colored neighbors of $v$ are only using $M/2$ different colors of $C_i$, with all these colors assigned evenly. Then, every such color itself would destroy a single vertex bin, and so the right-hand side of Equation 4 would be negative for nearly half of $h_1$. To fix this issue, we will first prune all those frequent neighbor colors away in a preprocessing step using a folklore deterministic algorithm for finding frequent items from [24]. Then, we show that the concentration bounds could work after such pruning steps.

The purpose of this procedure is to collect all the colors in $C_i\setminus F_v$ that are currently used frequently by $v$’s neighbors under partial coloring $\varphi$, which is done as following. For each vertex $v\in B_i,\forall 1\le i\le l$, make a pass over the graph stream and consider all the neighbors $u\in N(v)$ such that $\varphi (u)\in C_i\setminus F_v$. Apply Lemma 6 on the sub-stream of edges $\{\varphi (u)\in C_i\setminus F_v\mid u\in N(v)\}$ with space parameter $k=\lceil s^2\rceil$. This generates a list of colors $L_v=\{c\in C_i\setminus F_v\}$ of at most $s^2$ elements. Since there are at most $n/s^2$ uncolored vertices under $\varphi$, we can run all instances of the frequent item algorithm for all $v\in {\varphi }^{-1}(\perp )$ at the same time in a single pass over the input graph stream.After that, merge the list $F_v\leftarrow F_v\cup L_v$.

We are going to use almost $k$-wise independent hash functions to partition each bin $B_i$ and palette $C_i$ further. According to Lemma 9, by setting the parameters

we can find a $(k_1,{ϵ}_1)$-wise independent hash family ${\mathscr{H}}_1$ of size at most

Similarly, by setting the parameters

we can find a $(k_2,{ϵ}_2)$-wise independent hash family ${\mathscr{H}}_2$ of size at most

Our goal is to find a good pair of hash functions $(h_1^{\ast },h_2^{\ast })\in {\mathscr{H}}_1\times {\mathscr{H}}_2$ and partition each bin $B_j$ and palette $C_j$ as

where $B_{i,h_1}^j=\{v\in B_i\mid h_1^{\ast }(v)=j\},C_{i,h_2}^j=\{c\in C_i\mid h_2^{\ast }(c)=j\}$, such that we can verify Invariant 13 with the refined partitions.

The algorithm tries to find a good pair $(h_1,h_2)\in {\mathscr{H}}_1\times {\mathscr{H}}_2$ in the straightforward manner. Basically, the algorithm makes one pass over the input graph stream, and each vertex keeps a counter $\mathrm{𝖼𝗇𝗍}(v,h_1,h_2)$ for every pair $(h_1,h_2)\in {\mathscr{H}}_1\times {\mathscr{H}}_2$ which is equal to the value of
$$\mathrm{𝖼𝗇𝗍}(v,h_1,h_2)=\left|C_{i,h_2}^{h_1(v)}\setminus F_v\right|-\left(\left|\{u\in N(v)\mid u\in B_{i,h_1}^{h_1(v)}\}\right|+\left|\{u\in N(v)\mid \varphi (u)\in C_{i,h_2}^{h_1(v)}\setminus F_v\}\right|\right)$$

Maintaining the counter $\mathrm{𝖼𝗇𝗍}(v,h_1,h_2)$ is straightforward: when an edge $(u,v)$ from the input stream is read, we check if $u\in B_{i,h_1}^{h_1(v)}$ and $\varphi (u)\in C_{i,h_2}^{h_1(v)}\setminus F_v$ respectively and update $\mathrm{𝖼𝗇𝗍}(v,h_1,h_2)$ accordingly. Besides, we also check whether the second inequality is preserved under $(h_1,h_2)$ for $v$:

This decides whether a vertex is good or bad with respect to any pair $(h_1,h_2)$, so in the end we can find one good pair $(h_1,h_2)$ if it exists. The total required would be $|{\mathscr{H}}_1|\cdot |{\mathscr{H}}_2|=O(s^2{\log }^{6}n)$ for each pair, so the overall space would be $\tilde{O}(n)$ since $\left|{\varphi }^{-1}(\perp )\right|\le n/s^2$.

After we have found a good pair $(h_1^{\ast },h_2^{\ast })\in {\mathscr{H}}_1\times {\mathscr{H}}_2$ whose existence will be proven later, add all the bad vertices to $B_{\text{bad}}$, and update the vertex partition as:

where ${\tilde{B}}_{i,h_1^{\ast }}^j=\{v\in B_{i,h_1^{\ast }}^j\mid v\text{ is good}\}$.

As for the color partition, if some sub-palette $C_{i,h_2^{\ast }}^j$ has size larger than

then merge it with $C_{\text{bad}}$. All other sub-palettes $C_{i,h_2^{\ast }}^j$ stay in the partition:

Assume Invariant 13 is preserved at the beginning of every round. Let $t^{\ast }$ be the smallest integer such that

By definition, $M={\lfloor s^{1/200}\rfloor }_2>0.5\cdot 2^{\sqrt{\log \mathrm{\Delta }}}$, and so $t^{\ast }=O\left(\frac{\log \mathrm{\Delta }}{\log M}\right)=O\left(\frac{\log \mathrm{\Delta }}{\log s}\right)$. Then, after the $(t^{\ast }-1)$-th round, in the color partition $[(1+\eta )\mathrm{\Delta }]=C_{\text{bad}}\cup C_1\cup \mathrm{\cdots }\cup C_l$, for each $1\le i\le l$ we have:

Also, in the vertex partition ${\varphi }^{-1}(\perp )=B_{\text{bad}}\cup B_1\cup \mathrm{\cdots }\cup B_l$, for each $1\le i\le l$ and $v\in B_i$, we have:

Consequently, we have: