Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms

TY - GEN

T1 - Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms

AU - Assadi, Sepehr

AU - Chakrabarti, Amit

AU - Ghosh, Prantar

AU - Stoeckl, Manuel

N1 - Publisher Copyright: © 2023 ACM.

PY - 2023/6/18

Y1 - 2023/6/18

N2 - 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 semi-streaming (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 semi-streaming 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.

AB - 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 semi-streaming (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 semi-streaming 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.

KW - adversarial robustness

KW - data streams

KW - graph coloring

UR - http://www.scopus.com/inward/record.url?scp=85164249016&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85164249016&partnerID=8YFLogxK

U2 - 10.1145/3584372.3588681

DO - 10.1145/3584372.3588681

M3 - Conference contribution

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 141

EP - 153

BT - PODS 2023 - Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

PB - Association for Computing Machinery

T2 - 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023

Y2 - 18 June 2023 through 23 June 2023

ER -