Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available November 6, 2024

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 semistreaming 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 semistreaming model as well? We settle this key question in the affirmative by designing a randomizedsemistreaming 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 semistreaming algorithm thatuses $(i)$ a novel sparserecovery approach based on sparsedensedecompositions 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 semistreaming algorithms.We believe both these techniques can be of independent interest.

Megow, Nicole ; Smith, Adam (Ed.)Structural balance theory studies stability in networks. Given a nvertex complete graph G = (V,E) whose edges are labeled positive or negative, the graph is considered balanced if every triangle either consists of three positive edges (three mutual "friends"), or one positive edge and two negative edges (two "friends" with a common "enemy"). From a computational perspective, structural balance turns out to be a special case of correlation clustering with the number of clusters at most two. The two main algorithmic problems of interest are: (i) detecting whether a given graph is balanced, or (ii) finding a partition that approximates the frustration index, i.e., the minimum number of edge flips that turn the graph balanced. We study these problems in the streaming model where edges are given one by one and focus on memory efficiency. We provide randomized singlepass algorithms for: (i) determining whether an input graph is balanced with O(log n) memory, and (ii) finding a partition that induces a (1 + ε)approximation to the frustration index with O(n ⋅ polylog(n)) memory. We further provide several new lower bounds, complementing different aspects of our algorithms such as the need for randomization or approximation. To obtain our main results, we develop a method using pseudorandom generators (PRGs) to sample edges between independentlychosen vertices in graph streaming. Furthermore, our algorithm that approximates the frustration index improves the running time of the stateoftheart correlation clustering with two clusters (GiotisGuruswami algorithm [SODA 2006]) from n^O(1/ε²) to O(n²log³n/ε² + n log n ⋅ (1/ε)^O(1/ε⁴)) time for (1+ε)approximation. These results may be of independent interest.more » « less

Megow, Nicole ; Smith, Adam (Ed.)Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applications in streaming, distributed computing, and massively parallel algorithms, among others. Graph sketching has proven to be quite successful for various problems such as connectivity, minimum spanning trees, edge or vertex connectivity, and cut or spectral sparsifiers. Yet, the problem of approximating shortest path metric of a graph, and specifically computing a spanner, is notably missing from the list of successes. This has turned the status of this fundamental problem into one of the most longstanding open questions in this area. We present a partial explanation of this lack of success by proving a strong lower bound for a large family of graph sketching algorithms that encompasses prior work on spanners and many (but importantly not also all) related cutbased problems mentioned above. Our lower bound matches the algorithmic bounds of the recent result of Filtser, Kapralov, and Nouri (SODA'21), up to lower order terms, for constructing spanners via the same graph sketching family. This establishes nearoptimality of these bounds, at least restricted to this family of graph sketching techniques, and makes progress on a conjecture posed in this latter work.more » « less