An official website of the United States government
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 n-vertex 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, non-robust, 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 complexity-theoretic standpoint, these lower bounds provide (i) the first significant separation between adversarially robust algorithms and ordinary randomized algorithms for a natural problem on insertion-only 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
From Cliques to Colorings and Back Again
We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology. It relies on four sub-algorithms that alternatingly compute cliques of larger size and colorings with fewer colors. We show how these techniques can mutually help each other: larger cliques facilitate finding smaller colorings, which in turn can boost finding larger cliques. We evaluate our approach on the DIMACS graph coloring suite. For finding maximum cliques, we show that our algorithm can improve the state-of-the-art MaxSAT-based solver IncMaxCLQ, and for the graph coloring problem, we close two open instances, decrease two upper bounds, and increase one lower bound.
more »
« less
- PAR ID:
- 10357179
- Date Published:
- Journal Name:
- 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Quasi-cliques are dense incomplete subgraphs of a graph that generalize the notion of cliques. Enumerating quasi-cliques from a graph is a robust way to detect densely connected structures with applications in bioinformatics and social network analysis. However, enumerating quasi-cliques in a graph is a challenging problem, even harder than the problem of enumerating cliques. We consider the enumeration of top- k degree-based quasi-cliques and make the following contributions: (1) we show that even the problem of detecting whether a given quasi-clique is maximal (i.e., not contained within another quasi-clique) is NP-hard. (2) We present a novel heuristic algorithm K ernel QC to enumerate the k largest quasi-cliques in a graph. Our method is based on identifying kernels of extremely dense subgraphs within a graph, followed by growing subgraphs around these kernels, to arrive at quasi-cliques with the required densities. (3) Experimental results show that our algorithm accurately enumerates quasi-cliques from a graph, is much faster than current state-of-the-art methods for quasi-clique enumeration (often more than three orders of magnitude faster), and can scale to larger graphs than current methods.more » « less
-
Every graph with maximum degree $$\Delta$$ can be colored with $$(\Delta+1)$$colors using a simple greedy algorithm. Remarkably, recent work has shown thatone can find such a coloring even in the semi-streaming model. But, in reality,one almost never needs $$(\Delta+1)$$ colors to properly color a graph. Indeed,the celebrated \Brooks' theorem states that every (connected) graph besidecliques and odd cycles can be colored with $$\Delta$$ colors. Can we find a$$\Delta$$-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomizedsemi-streaming algorithm that given any graph, with high probability, eithercorrectly declares that the graph is not $$\Delta$$-colorable or outputs a$$\Delta$$-coloring of the graph. The proof of this result starts with a detour. We first (provably) identifythe extent to which the previous approaches for streaming coloring fail for$$\Delta$$-coloring: for instance, all these approaches can handle streams withrepeated edges and they can run in $o(n^2)$ time -- we prove that neither ofthese tasks is possible for $$\Delta$$-coloring. These impossibility resultshowever pinpoint exactly what is missing from prior approaches when it comes to$$\Delta$$-coloring. We then build on these insights to design a semi-streaming algorithm thatuses $(i)$ a novel sparse-recovery approach based on sparse-densedecompositions to (partially) recover the problematic subgraphs of the input-- the ones that form the basis of our impossibility results -- and $(ii)$ anew coloring approach for these subgraphs that allows for recoloring of othervertices in a controlled way without relying on local explorations or findingaugmenting paths that are generally impossible for semi-streaming algorithms.We believe both these techniques can be of independent interest.more » « less
-
Mulzer, Wolfgang; Phillips, Jeff M (Ed.)Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of ℝ² and let 𝒟 = {D_1,…,D_n} be a set of geodesic disks with respect to the metric d. We prove that 𝒢^×(𝒟), the intersection graph of the disks in 𝒟, has a clique-based separator consisting of O(n^{3/4+ε}) cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for q-Coloring that runs in time 2^O(n^{3/4+ε}), assuming the boundaries of the disks D_i can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses O(n^{7/4+ε}) storage and can report the hop distance between any two nodes in 𝒢^×(𝒟) in O(n^{3/4+ε}) time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.more » « less
-
Motivated by non-local games and quantum coloring problems, we introduce a graph homomorphism game between quantum graphs and classical graphs. This game is naturally cast as a “quantum–classical game,” that is, a non-local game of two players involving quantum questions and classical answers. This game generalizes the graph homomorphism game between classical graphs. We show that winning strategies in the various quantum models for the game is an analog of the notion of non-commutative graph homomorphisms due to Stahlke [IEEE Trans. Inf. Theory 62(1), 554–577 (2016)]. Moreover, we present a game algebra in this context that generalizes the game algebra for graph homomorphisms given by Helton et al. [New York J. Math. 25, 328–361 (2019)]. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the four coloring game for a quantum graph is always non-trivial, extending a result of Helton et al. [New York J. Math. 25, 328–361 (2019)].more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.CP.2022.26
