Alternative method for solving the graph coloring problem discovered

The graph coloring problem attempts to assign a color to nodes connected by links under the limitation that no two connected nodes can have the same color. The problem then asks what is the minimum number of colors needed for a given graph? This problem has useful applications in combinatorial optimization problems, such as timetabling.

In the same branch of mathematics, there are functional optimization problems, which are tackled by their own set of methods. Crnkić et al. formed a bridge between these two types of optimization problems to turn the combinatorial optimization problem of graph coloring into a functional optimization problem.

“In principle, we found a way to convert a problem of combinatorial optimization into a problem of functional optimization,” said author Zoran Levnajić. “This does not necessarily mean that combinatorial optimization problems will immediately be easier to solve. Instead, it means that combinatorial optimization problems are approachable via functional optimization methods in addition to combinatorial optimization methods.”

The authors found this unique way of conceptualizing the graph coloring problem by designing a set of interaction functions that couple phase oscillators on a graph.

“The trick to this method involves the model of repulsively coupled phase oscillators, whose natural dynamical evolution is nothing but the search for the optimal coloring solution,” said Levnajić. “In that sense, our algorithm for graph coloring appears as a distributed learning in a population of coupled oscillators.”

The authors look forward to studying whether this method can be applied to combinatorial problems other than the graph coloring problem.

Source: “Collective dynamics of phase-repulsive oscillators solves graph coloring problem,” by Aladin Crnkić, Janez Povh, Vladimir Jaćimović, and Zoran Levnajić, Chaos (2020). The article can be accessed at https://doi.org/10.1063/1.5127794 .