Vertex coloring of graphs via phase dynamics of coupled oscillatory networks

Abstract

While Boolean logic has been the backbone of digital information processing, there are classes of computationally hard problems wherein this conventional paradigm is fundamentally inefficient. Vertex coloring of graphs, belonging to the class of combinatorial optimization represents such a problem; and is well studied for its wide spectrum of applications in data sciences, life sciences, social sciences and engineering and technology. This motivates alternate, and more efficient non-Boolean pathways to their solution. Here, we demonstrate a coupled relaxation oscillator based dynamical system that exploits the insulator-metal transition in vanadium dioxide (VO2), to efficiently solve the vertex coloring of graphs. By harnessing the natural analogue between optimization, pertinent to graph coloring solutions, and energy minimization processes in highly parallel, interconnected dynamical systems, we harness the physical manifestation of the latter process to approximate the optimal coloring of k-partite graphs. We further indicate a fundamental connection between the eigen properties of a linear dynamical system and the spectral algorithms that can solve approximate graph coloring. Our work not only elucidates a physics-based computing approach but also presents tantalizing opportunities for building customized analog co-processors for solving hard problems efficiently.

References in corpus (5)

• Evidence for a Structurally-driven Insulator-to-metal Transition in VO2: a View from the Ultrafast Timescale
• Optimization hardness as transient chaos in an analog approach to constraint satisfaction
• Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
• Synchronization of pairwise-coupled, identical, relaxation oscillators based on metal-insulator phase transition devices: A Model Study
• An event-based architecture for solving constraint satisfaction problems

Cited by in corpus (13)

• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Memristive control of mutual SHNO synchronization for neuromorphic computing
• Origin of current-controlled negative differential resistance modes and the emergence of composite characteristics with high complexity
• Current localisation and redistribution as the basis of discontinuous current controlled negative differential resistance in NbOx
• Observation of Distinct Phase Transitions in a Nonlinear Optical Ising Machine
• Ultra-low Power Microwave Oscillators based on Phase Change Oxides as Solid-State Neurons
• On computational capabilities of Ising machines based on nonlinear oscillators,
• Memristive oscillatory circuits for resolution of NP-complete logic puzzles: Sudoku case
• Collective dynamics of phase-repulsive oscillators solves graph coloring problem
• Higher Order and Long-Range Synchronization Effects for Classification and Computing in Oscillator-Based Spiking Neural Networks
• Analysis of the Hopfield Model with Discrete Coupling
• Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization
• Scalable almost-linear dynamical Ising machines