Streaming Algorithms for Conflict-Free Coloring

The following results on conflict-free coloring are due to Pach and Tardos [23].

As a corollary of Proposition 2, it is proved that ${\chi }_{ON}(G)\le \frac{1}{2}+\sqrt{2n+\frac{1}{4}}$. Cheilaris gave an alternate proof to to this result [14].

From Example 4, we infer that the bound in Proposition 3 is asymptotically tight.

Pach and Tardos [23] showed that, for any graph $G$, ${\chi }_{CN}(G)=O({\ln }^{2}n)$ where $n$ is the number of vertices in $G$. Glebov, Szabó and Tardos [18] showed the existence of graphs $G$ with ${\chi }_{CN}(G)=\mathrm{\Omega }({\ln }^{2}n)$.

Our algorithm partitions the vertex set into two parts: Part A, which is made of vertices of degree at least $2c\ln n$ for some constant $c$, and Part B, which is the set of all the remaining vertices (which are of degree less than $2c\ln n$). Part A is further partitioned into two parts, namely $A^{\prime }$ and $A^{\prime \prime }$. The set $A^{\prime \prime }$ is made of all vertices in $A$ that have no neighbor in $B$. We choose a random coloring for the vertices in $A$ from a geometric distribution. Then, we will show that, with high probability, every vertex in $A^{\prime \prime }$ sees some color exactly once in its open and closed neighborhood.

Next, we construct a hypergraph $\mathscr{H}=(B,ℰ)$, where $ℰ=\{N_G[v]\cap B:v\in A^{\prime }\cup B\}\cup \{N_G(v)\cap B:v\in A^{\prime }\cup B,N_G(v)\cap B\ne \mathrm{\varnothing })\}$. Observe that the maximum degree of $\mathscr{H}$ is at most $2c\ln n$ and hence can be CF colored by the greedy procedure given in Proposition 1 using $2c\ln n+1$ colors. Finally, we observe that the union of the two colorings explained above (let this coloring be $c$) is a CFCN coloring of $G$ and obtain Result 1. Moreover, we observe that for many vertices, there is a unique color in its open neighborhood as well. More specifically, let $B_1=\{b\in B:N_G(b)\cap B=\mathrm{\varnothing }\}$. We prove that for any vertex $v\in V(G)\setminus B_1$, there is a unique colored vertex in $N_G(v)$. Also, notice that for all $b\in B_1$, $|N_G(b)|=O(\ln n)$ and $N_G(b)\subseteq A^{\prime }$. So in the semi-streaming algorithm, we store the neighborhood information of the vertices in $B_1$ and obtain a CFON coloring $c^{\prime }$ of the graph induced on $A^{\prime }\cup B_1$ using at most $O(\sqrt{n})$ colors. Then, the coloring $c_o$ defined as $c_o(v)=(c(v),c^{\prime }(v))$ for all $v$, is a CFON coloring of $G$ using $O(\sqrt{n}{\ln }^{2}n)$ colors. Here, for convenience, assume that $c^{\prime }(v)=1$ if $v\notin A^{\prime }\cup B_1$. This gives us the following result on CFON coloring.

From Proposition 3, we know that ${\chi }_{ON}(G)\le 2\sqrt{n}$. This bound is asymptotically tight due to Example 4. Our next result, whose proof has been moved to the appendix due to the paucity of space, is the following.

For a graph $G$, with maximum degree $\mathrm{\Delta }$, Pach and Tardos [23] in the year 2009 showed that ${\chi }_{CN}(G)=O({\ln }^{2+ϵ}\mathrm{\Delta })$ for any $ϵ>0$. As mentioned above, in 2014, Glebov, Szabó, and Tardos [18] proved that there exist graphs $G$ on $n$ vertices with ${\chi }_{CN}(G)=\mathrm{\Omega }({\ln }^{2}n)$ (and thereby $\mathrm{\Omega }({\ln }^2\mathrm{\Delta })$). In the year 2021, Bhyravarapu, Kalyanasundaram, and Mathew [12] tightened the upper bound to show that ${\chi }_{CN}(G)=O({\ln }^2\mathrm{\Delta })$. The methods we use in proving Result 1 give us an alternate, shorter proof (which is given below).

We partition $V(G)=A\uplus B,$ where $A=\{v\in V(G):de{g}_G(v)\ge 2t-1\}$, $B=V(G)\setminus A$ and $t=\ln \mathrm{\Delta }$. Further, let $A=A_1\uplus A_2$ where $A_1=\{a\in A:(N_G(a)\cap B)\ne \mathrm{\varnothing }\}$ and $A_2=A\setminus A_1$. We define a hypergraph ${\mathscr{H}}_2=(A,{ℰ}_2)$ where ${ℰ}_2=\{N_G[a]:a\in A_2\}$. From the definition of $A_2,N_G[a]\subseteq A,\forall a\in A_2$. Applying Proposition 2 with $t=\ln \mathrm{\Delta },\mathrm{\Gamma }={\mathrm{\Delta }}^2$, we get ${\chi }_{CN}({\mathscr{H}}_2)=O({\log }^2\mathrm{\Delta })$. This coloring of the vertices of $A$ ensures that every vertex in $A_2$ sees some color exactly once in its closed neighborhood in $G$. We define another hypergraph ${\mathscr{H}}_1=(B,{ℰ}_1),{ℰ}_1=\{N_G[v]\cap B:v\in A_1\cup B\}$. Since the degree of a vertex in $B$ in graph $G$ is at most $2\ln \mathrm{\Delta }-2$, we can conclude that every vertex in ${\mathscr{H}}_1$ is present in at most $2\ln \mathrm{\Delta }-1$ hyperedges. Applying Proposition 1 on ${\mathscr{H}}_1,$ we get ${\chi }_{CN}({\mathscr{H}}_1)\le 2\ln \mathrm{\Delta }$. We make sure that the set of colors used to color ${\mathscr{H}}_2$ is disjoint from the set of colors used to color ${\mathscr{H}}_1$. This coloring of the vertices of $B$ ensures that every vertex in $A_1\uplus B$ sees some color exactly once in its closed neighborhood in $G$. $◀$

It is known that ${\chi }_{ON}(G)\le \mathrm{\Delta }+1$, where $\mathrm{\Delta }$ is the maximum degree of a vertex in $G$ (follows from Proposition 1). From Example 4, we know that this bound is tight. Our next result is the following.

In our algorithm of Result 4, we use the pallete sparsification lemma of Assadi, Chen, and Khanna [4]. For each vertex $v\in V(G)$, we sample a set $L(v)$ of $O(\frac{1}{ϵ}\ln n)$ colors from $[(1+ϵ)\mathrm{\Delta }]$. In the first pass of the stream, for each vertex $v$, we identify a special vertex $s(v)$ that will get a unique color among $N_G(v)$ in our coloring. In the second pass, using the list of colors and special vertices, we find a sketch $H$ of $G$ of size $O(\frac{1}{{ϵ}^2}n{\ln }^{2}n)$. Finally, we do a greedy procedure on $H$ to get a CFON coloring.

We observe that any $O(1)$-pass streaming algorithm that determines if the CFCN (CFON) chromatic number of an input graph is at most $2$ or not, requires $\mathrm{\Omega }(n)$ space. The proofs of both the results are by reductions from the two player communication problem Disjointness (refer [20]). In this problem, Alice and Bob are given two strings of length $n$ (say the strings given to them are $p_1\mathrm{\dots }{p}_n$ and $q_1\mathrm{\dots }{q}_n$, respectively), and they are disjoint if there is no $i\in [n]$ such that $p_i=1$ and $q_i=1$. It is known that any protocol (even randomized) solving Disjointness requires at least $\mathrm{\Omega }(n)$ space.

Consider an instance $I$ of the Disjointness Problem where Alice is given an $n$-bit string $p_1\mathrm{\dots }{p}_n$ and Bob is given an $n$-bit string $q_1\mathrm{\dots }{q}_n$. Together they construct a graph $G(I)$ on $5n$ vertices whose vertices are $a_i,b_i,c_i,d_i,x_i$, where $1\le i\le n$. For every $i$, Alice adds the edges $a_i{b}_i$, $b_i{c}_i$, $c_i{d}_i$, $d_i{a}_i$ to form $n$ $4$-cycles. Further, for every $i$, (i) if $p_i=1$, then Alice adds the edge $b_i{x}_i$, and (ii) if $q_i=1$, then Bob adds the edge $c_i{x}_i$. For each $i$, they create one or two components of $G(I)$ which is isomorphic to one of the graphs in Figure 1. The graph when both the corresponding bits intersect (i.e., $p_i=q_i=1$) require at least 3 colors for any CFCN coloring. It can be verified that the graph $G(I)$ thus constructed has its CFCN chromatic number at most $2$ if and only if $I$ is a YES instance of the Disjointness problem. $◀$

For this purpose, given an instance $I$, Alice and Bob together construct a graph $H(I)$ on $6n$ vertices, namely $a_i,b_i,c_i,d_i,e_i,f_i$, $1\le i\le n$, as described below: For every $i$, Alice adds the edges $a_i{b}_i,c_i{d}_i,d_i{e}_i,e_i{f}_i$. Further, for every $i$, (i) if $p_i=1$, then Alice adds the edge $a_i{f}_i$, and (ii) if $q_i=1$, the Bob adds the edge $b_i{c}_i$. If there exists $i$ such that $p_i=q_i=1$, then $H(I)$ has a connected component which is a cycle of length 6 and we need at least 3 colors in any CFON coloring of it. Otherwise each connected component of $H(I)$ is a path and its CFON chromatic number is at most $2$. See Figure 2 for an illustration. $◀$

Proof follows from the application of Lemma 2 with ${\mathscr{H}}_1=({𝒱}_1,{ℰ}_1)$ defined as ${𝒱}_1=V(G_1)$ and ${ℰ}_1=\{N_{G_1}[v]:v\in X\}\cup \{N_{G_1}(v):v\in X\}$. $◀$

The hypergraph ${\mathscr{H}}_2$ constructed in step 1 of Algorithm 2 takes $O(n_2\ln r_2)$ space because the degree of this hypergraph is at most $8\lceil \ln r_2\rceil$. It is easy to see that a conflict-free coloring of ${\mathscr{H}}_2$ will ensure properties (a) and (b). Proposition 1 gives a conflict-free coloring of ${\mathscr{H}}_2$ in $O(n_2\ln r_2)$ time and $O(n_2\ln r_2)$ space using at most $8\lceil \ln r_2\rceil$ colors. $◀$

We apply Lemma 8 with the following inputs: $G_1=(A,E_1)$, where $E_1=\{(u,v):u,v\in A\}$, $X=A^{\prime \prime }$, $Y=A^{\prime }$, and $r_1=n$. The algorithm mentioned in Lemma 2, runs in $O(n{\ln }^{2}n)$ time, as $n_1\le r_1=n$. It uses $O(n)$ space and outputs the coloring function $c_1:A\to [16\lceil e{\ln }^{2}n\rceil ]$. With probability greater than $(1-\frac{2}{n})$, every vertex in $A^{\prime \prime }(=X)$ will see some color exactly once in its open and closed neighborhoods under the coloring $c_1$ (as well as in $c$).

Next, we invoke Algorithm 2 with the following inputs: the graph $G_2=(A^{\prime }\uplus B,E_2)$, where $X=A^{\prime }$, $Y=B$, $r_2=n$, and $E_2=E(G)\setminus E_1$. It is important to note that (i) $G_2$ is well-defined as every edge in $E_2$ has both its endpoints in $A^{\prime }\cup B$, and (ii) $A^{\prime }$ is an independent set in $G_2$. According to Lemma 9, Algorithm 2 outputs the coloring $c_2:B\to \{16\lceil e{\ln }^{2}n\rceil +1,\mathrm{\dots },16\lceil e{\ln }^{2}n\rceil +8\lceil \ln n\rceil \}$ in $O(n\ln n)$ time, using $O(n\ln n)$ space, since $n_2\le r_2=n$. By property (a) of Lemma 9, every vertex in $A^{\prime }\cup B$ sees some color exactly once in its closed neighborhood under the coloring $c_2$ (as well as in $c$). Therefore, we have proved that $c$ is a CFCN coloring of $G$.

Furthermore, based on the reasoning above, our algorithm takes $O(n{\ln }^{2}n)$ time and $O(n\ln n)$ space. We have already proved that with probability greater than $(1-\frac{2}{n})$, every vertex in $A^{\prime \prime }$ will see some color exactly once in its open neighborhoods under the coloring $c$. By the property $(b)$ of Lemma 9, we know that every vertex $v$ in $\{u\in V(G_2):N_{G_2}(u)\cap Y\ne \mathrm{\varnothing }\}=A^{\prime }\cup \{b\in B:N_G(b)\cap B\ne \mathrm{\varnothing }\}$, sees some vertex exactly once in its open neighborhood under the coloring $c_2$ (as well as in $c$). This proves property (ii) mentioned in the lemma. $◀$

The proof follows from the application of Lemma 10 and the following partitioning of the vertex set $V:=V(G)$. We start by partitioning the vertex set $V$ into two sets, namely $A$ and $B$, where $A=\{v\in V:{\text{deg}}_G(v)\ge (4\lceil \ln n\rceil -1)\}$ and $B=V\setminus A$ using the following procedure . Here, $A$ represents the set of high-degree vertices, while $B$ represents the set of low-degree vertices.

To facilitate the partitioning process, we maintain a list $L(v)=\{u:u\in N_G(v)\}$. Initially, we set $A:=\mathrm{\varnothing }$ and $L(v)=\mathrm{\varnothing }$. As each edge $(u,v)$ passes through the stream, we update $L(u)=L(u)\cup \{v\}$ if $u\in V\setminus A$ and $L(v)=L(v)\cup \{u\}$ if $v\in V\setminus A$. Additionally, if a vertex $w$ satisfies $|L(w)|\ge (4\lceil \ln n\rceil -1)$, then we update $A:=A\cup \{w\}$. At the end of the stream, we define $B:=V\setminus A$. It is important to note that for any vertex $b\in B$, . Up to this point, the storage requirement for $\bigcup _{v\in V}L(v)$ is $O(n\ln n)$ space.

Next, for all $a\in A$, update $L(a)$ as $L(a)=\{b\in B:a\in L(b)\}$. That is $L(a)$ is the set $N_G(a)\cap B$. Observe that updating $L(a)$’s can only double the total space used so far. After updating $L(a)$, for all $a\in A$, we define $A^{\prime }=\{a\in A:L(a)\ne \mathrm{\varnothing }\}$ and $A^{\prime \prime }=A\setminus A^{\prime }$. We have thus obtained (i) the sets $A^{\prime },A^{\prime \prime },B$, (ii) $N_G(a^{\prime })\cap B$, for all $a^{\prime }\in A^{\prime }$, and (iii) $N_G(b)$ for all $b\in B$. We can now invoke Algorithm 3 with the required inputs to obtain a CFCN coloring function $c:V(G)\to [16\lceil e{\ln }^{2}n\rceil +8\lceil \ln n\rceil ]$. From Lemma 10, we know that Algorithm 3 requires only $O(n\ln n)$ space and runs in polynomial time. $◀$

Given a graph $G=(V,E)$, we follow the same partitioning procedure mentioned in Theorem 5. That is, $A=\{v\in V:{\text{deg}}_G(v)\ge (4\lceil \ln n\rceil -1)\}$, and $B=V(G)\setminus A$. We again partition $B\subseteq V$ into two sets: $B=B_1\uplus B_2$, where $B_1=\{b\in B:N_G(b)\cap B=\mathrm{\varnothing }\}$ and $B_2=B\setminus B_1$ That is, using similar steps as in the case of Theorem 5, we get the partition of $V(G)$ into $A^{\prime }\uplus A^{\prime \prime }\uplus B_1\uplus B_2$. Moreover, we also get $L(b)=N_G(b)$ for all $b\in B$ in $O(n\ln n)$ space. Now we invoke Algorithm 3 with the required inputs to obtain a coloring $c:V(G)\to [16\lceil e{\ln }^{2}n\rceil +8\lceil \ln n\rceil ]$. From Lemma 10, we know that Algorithm 3 requires only $O(n\ln n)$ space and runs in polynomial time. Moreover, with probability greater than $1-\frac{2}{n}$, for every $v\in V(G)\setminus \{b\in B:N_G(b)\cap B=\mathrm{\varnothing }\}$, $v$ sees some color exactly once in its open neighbourhood.

We now invoke Proposition 3 (or an algorithmic version of it (see Theorem 18)) on the graph $G^{\prime }=(A^{\prime }\cup B_1,E^{\prime })$ where $E^{\prime }=\{(a,b)\in E(G):a\in A^{\prime },b\in B_1\}$ and get a CFON coloring $c^{\prime }:V(G^{\prime })\to [\lceil 2\sqrt{n}\rceil ]$ of $G^{\prime }$. Notice that $|E^{\prime }|=O(n\ln n)$ and hence $c^{\prime }$ can be obtained in $O(n\ln n)$ space and polynomial time (see Theorem 18). Now, consider the coloring $c_o$ on $V(G)$ defined as follows.

Now it is easy to see that $c_o$ is a CFON coloring because for each $v\in V(G)\setminus B_1$, there is a unique color in the open neighborhood of $v$ due to the coloring $c$ and for each $v\in B_1$, there is a unique color in the open neighborhood of $v$ due to the coloring $c^{\prime }$. Notice that the number of colors used in $c_o$ is $O(\sqrt{n}{\ln }^{2}n)$. $◀$

Suppose Algorithm 4 outputs a coloring $c$. To prove that it is a CFON coloring of $G$, we need to prove that for each $v\in V(G)$, there is a vertex in $N_G(v)$ with unique color. We will prove that for each vertex $v\in V(G)$, $s(v)$ becomes the uniquely colored vertex in $N_G(v)$. Recall that $s(v)$ is the first vertex in $\mathrm{\Pi }$ among $N_G(v)$. So Algorithm 4 colors $s(v)$ before coloring the vertices in $N_G(v)\setminus \{s(v)\}$. Step 6 of Algorithm 4 implies that each vertex in $N_G(v)\setminus \{s(v)\}$ gets a color different from the color of $s(v)$. So, $c$ is the CFON coloring of $G$.

We now find the probability that Algorithm 4 reports fail. Suppose Algorithm 4 reports FAIL in the $i$th iteration of step $6$. It means that $Z_i=\mathrm{\varnothing }$. That is, $L(v_i)\subseteq \{c(x)|x\in S_i\}$. We know that $|S_i|\le |N_G(v_i)|\le \mathrm{\Delta }$. Here, we want to calculate $\mathrm{Pr}[L(v_i)\subseteq S_i]$. This is calculated as follows.

Here, the second inequality follows from the fact that $|S_i|\le \mathrm{\Delta }$. Notice that there are $n$ iterations, and by the union bound, the probability that the algorithm reports FAIL in any one of these iterations is at most $\frac{1}{n^3}$. $◀$

We run Algorithm 4 $\ln n$ times parallelly. In each execution of the algorithm, if the space used by it exceeds $\frac{1600}{{ϵ}^2}n\ln n$, then we abort it. Finally, if any of the execution outputs a coloring, we output one such coloring. Otherwise, we output FAIL. The probability that each execution is either aborted or output FAIL is upper bounded by $\frac{1}{100}+\frac{1}{n^3}\le 0.02$. The probability that all the executions fail with probability is at most ${0.02}^{\ln n}\le \frac{1}{n^3}$. This implies that the overall probability that Algorithm 4 succeeds is at least $(1-\frac{1}{n^3})$. Notice that each execution of Algorithm 4 takes $O(\frac{1}{{ϵ}^2}n{\ln }^{2}n)$ space and hence the total space is $O(\frac{1}{{ϵ}^2}n{\ln }^{3}n)$. $◀$