Collective dynamics of phase-repulsive oscillators solves graph coloring problem

Abstract

We show how to couple phase-oscillators on a graph so that collective dynamics "searches" for the coloring of that graph as it relaxes toward the dynamical equilibrium. This translates a combinatorial optimization problem (graph coloring) into a functional optimization problem (finding and evaluating the global minimum of dynamical non-equilibrium potential, done by the natural system's evolution). Using a sample of graphs, we show that our method can serve as a viable alternative to the traditional combinatorial algorithms. Moreover, we show that, with the same computational cost, our method efficiently solves the harder problem of improper coloring of weighed graphs.

References in corpus (16)

• Synchronization in complex networks
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computing
• The Kuramoto model in complex networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Quantum Simulations of Classical Annealing Processes
• Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
• Phase resetting of collective rhythm in ensembles of oscillators
• Ramsey numbers and adiabatic quantum computing
• Emergent multistability and frustration in phase-repulsive networks of oscillators
• Graph isomorphism and adiabatic quantum computing
• Constrained quantum annealing of graph coloring
• First-order phase transitions in the Kuramoto model with compact bimodal frequency distributions
• Desynchronization and pattern formation in a noisy feedforward oscillators network
• Synchronization Patterns in Geometrically Frustrated Turing Rings