In the graph semi-streaming model, the edges of a graph on $n$ vertices are arriving one by one in a stream and the algorithm is only allowed to make one pass over this stream and use a memory of $O(n \operatorname{polylog}(n))$ to process the stream, namely proportional to number of vertices and hence much smaller than the size of the graph which can be $\Omega(n^2)$. A recent work has shown that $\Delta+1$ coloring of a graph with maximum degree $\Delta$ admits a semi-streaming algorithm. This algorithm however is randomized in a crucial way. The goal of this project is to investigate possibility of obtaining the same (or even somewhat weaker) result using a deterministic algorithm.
This project is being performed as part of the 2021 DIMACS REU at Rutgers University, and is supported by NSF grant CCF-1836666. This project website is maintained by the student contributor.
The student and advisor met for the first time. Due to conflicts with the student's university schedule, the majority of the work performed related only to reviewing relevant articles, such as [ACK19] and [Mau21].
Due to continued schedule conflicts, preliminary work remained the focus. Related problems (such as independent set) and connections between the streaming model and distributed CONGEST model were discussed. An idea to solve $O(k\Delta)$-coloring by partitioning the vertex set into $k$ subsets with $\widetilde{O}(n)$ internal edges was proposed.
Due to continued schedule conflicts, preliminary work remained the focus. The partitioning idea was investigated and initial roadblocks were identified. Although we believe the idea is heuristically good, difficulties and potential counterexamples were discovered.
We showed that any collection of partitions that works must have size at least $\Omega(\log_\Delta(n))$. We discussed more avenues through with to view the problem, including identifying whether or not certain properties such as expansion make the claim easier, and if we could solve the related communication problem, or even indepedent set communication problem.
We reached an exciting development by identifying a lower bound for the number of colors any streaming algorithm must use. The technique involves considering independent set in the communication model, as mentioned last week, and relies on a key lemma bounding the number of edges in a certain union of graphs. Our calculations were rough, so it remains to formally typeset and verify the proof.
By formally typesetting the proof of the lower bound result, we discovered a few caveats and the resulting bound is slightly weakened. The end result is that $O(n^{1 - \epsilon})$ colors is not possible when $\Delta = \Omega(n^{4/5})$. We also thought more about obtaining positive results through the partitioning idea, and through counting the number of allowed edges in the partitions, realized that this was unlikely to work.
We discussed the caveats identified in the previous week and were able to recover a stronger result for when $\Delta = \Omega(n^{2/3})$. This proves that no deterministic semi-streaming algorithm can color graphs using $\Delta^{3/2 - \epsilon}$ colors.
We discussed the gap between the $\Delta^{3/2}$ lower bound we have and the fact that our method potentially extends to $\Delta^2$ by a more refined description of the missing edges in the union graph. In particular, we explored describing the missing degrees, but this does not seem to work.
Due to the REU's official conclusion at the end of this week, we focused on preparing a final paper and presentation. However, we intend to continue discussing this topic past the official end of the REU.