An official website of the United States government
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
Improving the Speed and Quality of Parallel Graph Coloring
Graph coloring assigns a color to each vertex of a graph such that no two adjacent vertices get the same color. It is a key building block in many applications. In practice, solutions that require fewer distinct colors and that can be computed faster are typically preferred. Various coloring heuristics exist that provide different quality versus speed tradeoffs. The highest-quality heuristics tend to be slow. To improve performance, several parallel implementations have been proposed. This paper describes two improvements of the widely used LDF heuristic. First, we present a “shortcutting” approach to increase the parallelism by non-speculatively breaking data dependencies. Second, we present “color reduction” techniques to boost the solution of LDF. On 18 graphs from various domains, the shortcutting approach yields 2.5 times more parallelism in the mean, and the color-reduction techniques improve the result quality by up to 20%. Our deterministic CUDA implementation running on a Titan V is 2.9 times faster in the mean and uses as few or fewer colors as the best GPU codes from the literature.
more »
« less
- Award ID(s):
- 1955367
- PAR ID:
- 10435836
- Date Published:
- Journal Name:
- ACM Transactions on Parallel Computing
- Volume:
- 9
- Issue:
- 3
- ISSN:
- 2329-4949
- Page Range / eLocation ID:
- 1 to 35
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
We design and implement parallel graph coloring algorithms on the GPU using two different abstractions—one data-centric (Gunrock), the other linear-algebra-based (GraphBLAS). We analyze the impact of variations of a baseline independent-set algorithm on quality and runtime. We study how optimizations such as hashing, avoiding atomics, and a max-min heuristic affect performance. Our Gunrock graph coloring implementation has a peak 2x speed-up, a geomean speed-up of 1.3x and produces 1.6x more colors over previous hardwired state-of-the-art implementations on real-world datasets. Our GraphBLAS implementation of Luby's algorithm produces 1.9x fewer colors than the previous state-of-the-art parallel implementation at the cost of 3x extra runtime, and 1.014x fewer colors than a greedy, sequential algorithm with a geomean speed-up of 2.6x.more » « less
-
We design and implement parallel graph coloring algorithms on the GPU using two different abstractions—one datacentric (Gunrock), the other linear-algebra-based (GraphBLAS). We analyze the impact of variations of a baseline independent-set algorithm on quality and runtime. We study how optimizations such as hashing, avoiding atomics, and a max-min heuristic affect performance. Our Gunrock graph coloring implementation has a peak 2x speed-up, a geomean speed-up of 1.3x and produces 1.6x more colors over previous hardwired state-of-theart implementations on real-world datasets. Our GraphBLAS implementation of Luby’s algorithm produces 1.9x fewer colors than the previous state-of-the-art parallel implementation at the cost of 3x extra runtime, and 1.014x fewer colors than a greedy, sequential algorithm with a geomean speed-up of 2.6x.more » « less
-
Satisfiability (SAT) solving has become an important technology in computer-aided mathematics with various successes in number and graph theory. In this paper we apply SAT solvers to color infinitely long strips in the plane with a given height and number of colors. The coloring is constrained as follows: two points that are exactly unit distance apart must be colored differently. To finitize the problem, we tile the strips and all points on a tile have the same color. We evaluated our approach using two different tile shapes: squares and hexagons. The visualization of bounded height strips using 3 to 6 colors reveal patterns that are similar to the best known lower bounds for infinite strips. Our method can be a useful tool for mathematicians to search for patterns that can be generalized to infinite strips and allowed us to increase the lower bound for the strip height with 5 colors to an improved height of 1.700084.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1145/3543545
