2026-07-21T19:24:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20183 2024-07-02T07:52:50Z ddc:004 open_access

Streaming Edge Coloring with Subquadratic Palette Size Chechik, Shiri Mukhtar, Doron Zhang, Tianyi graph algorithms streaming algorithms edge coloring In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an n-node graph arrive in an arbitrary order to a machine with a relatively small space, and the goal is to design an algorithm that outputs, as a stream, a proper coloring of the edges using the fewest possible number of colors. Behnezhad et al. [Behnezhad et al., 2019] devised the first non-trivial algorithm for this problem, which computes in Õ(n) space a proper O(Δ²)-coloring w.h.p. (here Δ is the maximum degree of the graph). Subsequent papers improved upon this result, where latest of them [Ansari et al., 2022] showed that it is possible to deterministically compute an O(Δ²/s)-coloring in O(ns) space. However, none of the improvements succeeded in reducing the number of colors to O(Δ^{2-ε}) while keeping the same space bound of Õ(n). In particular, no progress was made on the question of whether computing an O(Δ)-coloring is possible with roughly O(n) space, which was stated in [Behnezhad et al., 2019] to be an interesting open problem. In this paper we bypass the quadratic bound by presenting a new randomized Õ(n)-space algorithm that uses Õ(Δ^{1.5}) colors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shiri Chechik and Doron Mukhtar and Tianyi Zhang 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.40 urn:nbn:de:0030-drops-201831 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.40 eng https://creativecommons.org/licenses/by/4.0/legalcode