The Math World Has a Serious Problem: Coloring (Yes, Coloring)
By LIDA TUNESI
Kids learning geography are sometimes asked to color in maps of countries. For visual clarity, it’s best if different colors are used for neighboring countries. Though it seems like a simple exercise, this is similar to a well-known, difficult problem in mathematics. The “graph coloring problem” is hard to solve even on powerful computers because the number of possible answers can be enormous.
Now, a paper by Ph.D. student Mostafa Honari-Latifpour and Professor Mohammad-Ali Miri (The Graduate Center, Queens College) presents a new way to solve this type of problem, using laser physics. Their work appears in Nanophotonics.
The method has implications for any field in which people need to solve combinatorial optimization problems, the authors say, like finance, computational biology, and even scheduling.
“Having a machine that can efficiently solve computationally hard problems allows us to find solutions to very large optimization problems that are otherwise intractable,” Miri said.
The problem is complicated even for a simple-looking diagram like the Petersen graph. If you were to color each point, or “node,” on the graph with one of three colors, there could be as many as 59,049 different options. A graph with 20 nodes could have more than three billion possibilities. Finding the best way to color the graph so that no connected nodes are the same color is like looking for a needle in a haystack, Honari-Latifpour said.
Rather than searching for the answer, Miri and Honari-Latifpour propose creating an optical system that naturally evolves toward the solution. They would use optical oscillators, which are similar to lasers, to represent graph nodes. The oscillators emit light in three different “phases,” which can be thought of as three different colors. When you turn one optical oscillator on, it randomly picks a color. But when you connect two or more oscillators, they affect each other and tend toward a state where connected oscillators emit different colors. Connect a bunch of oscillators in the same pattern as your graph, turn them on, and they would light up in a color pattern that solves your problem.
Like any physical system, the connected oscillators can be represented by math equations. This allowed the researchers to devise a second way of solving these problems—by feeding these equations into a computer.