A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may observe and react to the past outputs of the algorithm. We grow the burgeoning body of work on such algorithms in a new direction by studying robust algorithms for the problem of maintaining a valid vertex coloring of an nvertex graph given as a stream of edges. Following standard practice, we focus on graphs with maximum degree at most Δ and aim for colorings using a small number f(Δ) of colors.
A recent breakthrough (Assadi, Chen, and Khanna; SODA 2019) shows that in the standard, nonrobust, streaming setting, (Δ+1)colorings can be obtained while using only Õ(n) space. Here, we prove that an adversarially robust algorithm running under a similar space bound must spend almost Ω(Δ²) colors and that robust O(Δ)coloring requires a linear amount of space, namely Ω(nΔ). We in fact obtain a more general lower bound, trading off the space usage against the number of colors used. From a complexitytheoretic standpoint, these lower bounds provide (i) the first significant separation between adversarially robust algorithms and ordinary randomized algorithms for a natural problem on insertiononly streams and (ii) the first significant separation between randomized and deterministic coloring algorithms for graph streams, since deterministic streaming algorithms are automatically robust.
We complement our lower bounds with a suite of positive results, giving adversarially robust coloring algorithms using sublinear space. In particular, we can maintain an O(Δ²)coloring using Õ(n √Δ) space and an O(Δ³)coloring using Õ(n) space.
more »
« less
This content will become publicly available on January 1, 2025
LowMemory Algorithms for Online Edge Coloring
For edge coloring, the online and the Wstreaming models seem somewhat orthogonal: the former needs edges to be assigned colors immediately after insertion, typically without any space restrictions, while the latter limits memory to be sublinear in the input size but allows an edge’s color to be announced any time after its insertion. We aim for the best of both worlds by designing smallspace online algorithms for edge coloring.
Our online algorithms significantly improve upon the memory used by prior ones while achieving an O(1)competitive ratio. We study the problem under both (adversarial) edge arrivals and vertex arrivals. Under vertex arrivals of any nnode graph with maximum vertexdegree Δ, our online O(Δ)coloring algorithm uses only semistreaming space (i.e., Õ(n) space, where the Õ(.) notation hides polylog(n) factors). Under edge arrivals, we obtain an online O(Δ)coloring in Õ(n√Δ) space. We also achieve a smooth colorspace tradeoff: for any t = O(Δ), we get an O(Δt(log²Δ))coloring in Õ(n√{Δ/t}) space, improving upon the state of the art that used Õ(nΔ/t) space for the same number of colors.
The improvements stem from extensive use of random permutations that enable us to avoid previously used colors. Most of our algorithms can be derandomized and extended to multigraphs, where edge coloring is known to be considerably harder than for simple graphs.
more »
« less
 Award ID(s):
 1918989
 NSFPAR ID:
 10545361
 Editor(s):
 Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola
 Publisher / Repository:
 Schloss Dagstuhl – LeibnizZentrum für Informatik
 Date Published:
 Volume:
 297
 ISSN:
 18688969
 ISBN:
 9783959773225
 Page Range / eLocation ID:
 297297
 Subject(s) / Keyword(s):
 Edge coloring streaming model online algorithms Mathematics of computing → Graph coloring Theory of computation → Streaming, sublinear and near linear time algorithms
 Format(s):
 Medium: X Size: 19 pages; 867827 bytes Other: application/pdf
 Size(s):
 19 pages 867827 bytes
 Right(s):
 Creative Commons Attribution 4.0 International license; info:eurepo/semantics/openAccess
 Sponsoring Org:
 National Science Foundation
More Like this


Vizing’s celebrated theorem asserts that any graph of maximum degree ∆ admits an edge coloring using at most ∆ + 1 colors. In contrast, BarNoy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2∆−1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to lowdegree graphs, with ∆ = O(log n), and they conjectured the existence of online algorithms using ∆(1 + o(1)) colors for ∆ = ω(log n). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS’03 and Bahmani et al., SODA’10). We resolve the above conjecture for adversarial vertex arrivals in bipartite graphs, for which we present a (1+o(1))∆edgecoloring algorithm for ∆ = ω(log n) known a priori. Surprisingly, if ∆ is not known ahead of time, we show that no (e/(e−1)−Ω(1))∆edgecoloring algorithm exists.We then provide an optimal, (e/(e−1) +o(1))∆edgecoloring algorithm for unknown ∆ = ω(log n). Key to our results, and of possible independent interest, is a novel fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a nearlossless online rounding scheme, yielding our optimal randomized algorithms.more » « less

Graph coloring is a fundamental problem with wide reaching applications in various areas including ata mining and databases, e.g., in parallel query optimization. In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The initial algorithms in this line of work are all crucially randomized, raising natural questions about how important a role randomization plays in streaming graph coloring. A couple of very recent works prove that deterministic or even adversarially robust coloring algorithms (that work on streams whose updates may depend on the algorithm's past outputs) are considerably weaker than standard randomized ones. However, there is still a significant gap between the upper and lower bounds for the number of colors needed (as a function of the maximum degree Δ) for robust coloring and multipass deterministic coloring. We contribute to this line of work by proving the following results. In the deterministic semistreaming (i.e., O(n · polylog n) space) regime, we present an algorithm that achieves a combinatorially optimal (Δ+1)coloring using O(logΔ log logΔ) passes. This improves upon the prior O(Δ)coloring algorithm of Assadi, Chen, and Sun (STOC 2022) at the cost of only an O(log logΔ) factor in the number of passes. In the adversarially robust semistreaming regime, we design an O(Δ5/2)coloring algorithm that improves upon the previously best O(Δ3)coloring algorithm of Chakrabarti, Ghosh, and Stoeckl (ITCS 2022). Further, we obtain a smooth colors/space tradeoff that improves upon another algorithm of the said work: whereas their algorithm uses O(Δ2) colors and O(nΔ1/2) space, ours, in particular, achieves (i)~O(Δ2) colors in O(nΔ1/3) space, and (ii)~O(Δ7/4) colors in O(nΔ1/2) space.more » « less

Chan, Timothy ; Fischer, Johannes ; Iacono, John ; Herman, Grzegorz (Ed.)We study fundamental directed graph (digraph) problems in the streaming model. An initial investigation by Chakrabarti, Ghosh, McGregor, and Vorotnikova [SODA'20] on streaming digraphs showed that while most of these problems are provably hard in general, some of them become tractable when restricted to the wellstudied class of tournament graphs where every pair of nodes shares exactly one directed edge. Thus, we focus on tournaments and improve the state of the art for multiple problems in terms of both upper and lower bounds. Our primary upper bound is a deterministic singlepass semistreaming algorithm (using Õ(n) space for nnode graphs, where Õ(.) hides polylog(n) factors) for decomposing a tournament into strongly connected components (SCC). It improves upon the previously bestknown algorithm by Baweja, Jia, and Woodruff [ITCS'22] in terms of both space and passes: for p ⩾ 1, they used (p+1) passes and Õ(n^{1+1/p}) space. We further extend our algorithm to digraphs that are close to tournaments and establish tight bounds demonstrating that the problem’s complexity grows smoothly with the "distance" from tournaments. Applying our SCCdecomposition framework, we obtain improved  and in some cases, optimal  tournament algorithms for s,treachability, strong connectivity, Hamiltonian paths and cycles, and feedback arc set. On the other hand, we prove lower bounds exhibiting that some wellstudied problems  such as (exact) feedback arc set and s,tdistance  remain hard (require Ω(n²) space) on tournaments. Moreover, we generalize the former problem’s lower bound to establish spaceapproximation tradeoffs: any singlepass (1± ε)approximation algorithm requires Ω(n/√{ε}) space. Finally, we settle the streaming complexities of two basic digraph problems studied by prior work: acyclicity testing of tournaments and sink finding in DAGs. As a whole, our collection of results contributes significantly to the growing literature on streaming digraphs.more » « less

Megow, Nicole ; Smith, Adam (Ed.)The celebrated IP = PSPACE Theorem gives an efficient interactive proof for any boundedspace algorithm. In this work we study interactive proofs for nondeterministic bounded space computations. While Savitch’s Theorem shows that nondeterministic boundedspace algorithms can be simulated by deterministic boundedspace algorithms, this simulation has a quadratic overhead. We give interactive protocols for nondeterministic algorithms directly to get faster verifiers. More specifically, for any nondeterministic space S algorithm, we construct an interactive proof in which the verifier runs in time Õ(n+S²). This improves on the best previous bound of Õ(n+S³) and matches the result for deterministic space bounded algorithms, up to polylog(S) factors. We further generalize to alternating bounded space algorithms. For any language L decided by a time T, space S algorithm that uses d alternations, we construct an interactive proof in which the verifier runs in time Õ(n + S log(T) + S d) and the prover runs in time 2^O(S). For d = O(log(T)), this matches the best known interactive proofs for deterministic algorithms, up to polylog(S) factors, and improves on the previous best verifier time for nondeterministic algorithms by a factor of log(T). We also improve the best prior verifier time for unbounded alternations by a factor of S. Using known connections of bounded alternation algorithms to bounded depth circuits, we also obtain faster verifiers for bounded depth circuits with unbounded fanin.more » « less