{'fraction_non_alphanumeric': 0.019717261904761904, 'fraction_numerical': 0.0, 'mean_word_length': 4.85838779956427, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graph Coloring Using State Space Search

As a subject with many applications, graph coloring is one of the most studied NP-hard problems. Due to its time complexity, graph coloring is an excellent candidate for implementation with a parallelized architecture, and as such has become our choice for our project. Of the many ways that graph coloring can be adapted for parallel programming there are two main approaches in literature: the iterative and state-space search methods. The iterative approach begins by dividing the vertices of the graph to be colored into different groups, each of which is assigned to a node in the cluster. In the context of Charm++, this would be akin to dividing the vertices among a set of chares. At this point each chare would independently color its assigned vertices, and once all vertices had been colored the chares would communicate with each other to see if each of their respective vertices had any neighbors on other chares that violate the constraints of the coloring problem. Once color conflicts have been assessed, the chares would seek to mediate these problems through another round of independent coloring among the chares, a process that would be repeated until the graph has been successfully colored or shown to be uncolorable with the given number of colors. An example implementation is present by Boman et al. [?]. In contrast, the state-space search method seeks to start with the initial graph and color it by creating child chares for each possible color assignment among the vertices. This process of coloration and child creation is repeated until a solution to the coloring problem is found or an exhaustive search has yielded no solution. By doing so, the program explores all different possible colorations of the graph for a given number of colors. A state-space search exploration could find only the first valid solution and terminate; find all possible solutions; or find the most optimal solution among all possibilities. Sun et al. [?] have developed a general framework for solving state-space search problems like graph coloring and N-Queens. State-space search has an advantage over the iterative approach in that it does not require the large number of message exchanges between chares to mediate coloring conflicts. However, the state-space search does require the use of many more chares than the iterative approach and could incur higher memory overhead. Given the Charm runtime features likes load balancing, prioritized message execution and the general emphasis on over-decomposition, we implement the state-space approach for finding the first valid coloring of an input graph, with a given number of colors.