Vertex coloring of graphs via phase dynamics of coupled oscillatory networks

Abstract

While Boolean logic has been the backbone of digital information processing, there exist classes of computationally hard problems wherein this paradigm is fundamentally inefficient. Vertex coloring of graphs, belonging to the class of combinatorial optimization, represents one such problem. It is well studied for its applications in data sciences, life sciences, social sciences and technology, and hence, motivates alternate, more efficient non-Boolean pathways towards its solution. Here we demonstrate a coupled relaxation oscillator based dynamical system that exploits insulator-metal transition in Vanadium Dioxide (VO₂) to efficiently solve vertex coloring of graphs. Pairwise coupled VO₂ oscillator circuits have been analyzed before for basic computing operations, but using complex networks of VO₂ oscillators, or any other oscillators, for more complex tasks have been challenging in theory as well as in experiments. The proposed VO₂ oscillator network harnesses the natural analogue between optimization problems and energy minimization processes in highly parallel, interconnected dynamical systems to approximate optimal coloring of graphs. We further indicate a fundamental connection between spectral properties of linear dynamical systems and spectral algorithms for 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.

Figure 1

Overview of the circuit and system dynamics. (a) Overview of the proposed system for vertex coloring and a simulation example. First step is a coupled relaxation oscillator circuit where the oscillators are composed of a series combination of VO₂ device and a resistor (with a loading capacitor in parallel), and are connected in a graph using capacitors. The equivalent circuit diagram of the VO₂ oscillator is shown using an internal capacitance c_i and a phase changing conductance g_(m/i) which switches between metallic conductance g_m and insulating conductance g_i. An example 3-partite graph is simulated and the relative phases of these oscillators are shown in a phase diagram which shows vertex color-sorting in phase, and can be used to calculate vertex-coloring with O(n²) complexity. (b) The circuit is composed of VO₂ oscillators capacitively coupled in a network same as the input graph. The final order of phases, or charging spikes, of the oscillators is related to the eigenvectors of the adjacency matrix of the input graph which in turn are related to the solution of the graph coloring problem.

Figure 2

Coupled oscillator circuit schematic. A circuit of 4 coupled oscillators with capacitive connections between oscillators controlled using switches corresponding to the adjacency matrix A and coupling capacitance c_c. The subscripts denote the corresponding entries in A. Note that A_ij = A_ji, A_ii = 0 and A_ij ∈ {0,1}.

Figure 3

Phase dynamics of synchronized VO₂ based capacitively coupled relaxation oscillators. (a,b) Schematics of two representative configurations (a: delta configuration; b: cross-connected ring) of capacitively coupled VO₂ based oscillators, and their corresponding graphs. (c,d) Time domain waveforms from experiment and simulations for the two coupled oscillator configurations in (a,b), respectively, showing that while the oscillators are synchronized in frequency, no two directly coupled oscillators are in-phase. This important property of the coupled oscillator system enables graph coloring. (e,f) Time averaged XOR of thresholded outputs of oscillators (each w.r.t. oscillator number 1), and respective polar phase plots showing steady state relative phases detected using PFDs. The XOR values are normalized with respect to the maximum value.

Figure 4

Experimental results of graph coloring using coupled VO₂ based oscillators. Various graph configurations, and their experimentally obtained solutions (PFD outputs and XOR values) using the coupled relaxation oscillator system. After mapping the graphs onto the coupled oscillator hardware, the steady state order of phases of oscillators is used as a color-sorting and a color assignment is calculated.

Figure 5

System dynamics and asymptotic permutation. (a) Simulation waveforms of a circuit connected in the 3-partite graph shown in Fig. 1a. The gray regions show the time when the system is in state s = 0. (b) Representative figure showing the relation between the asymptotic order of components of the state vector and the eigenspaces in a two-dimensional linear system where the coefficient matrix has negative eigenvalues.

Figure 6

Effect of hardness on circuit behavior. (Above) Graph diagram and (below) waveforms of permutation number (a unique number corresponding to each permutation) of charging spikes and number of colors detected with time. All graphs are 3-partite with partition (8,2,10) with varying levels of average connectivity: (a) 1.0, (b) 0.57 and (c) 0.48. All triangles in the graph are shown with red edges and the rest edges are shown in blue.

Figure 7

Simulation results on random graph instances. (a) Maximum cluster diameter for those graphs for which 3 colors were detected. (b) (Top) Number of colors detected plotted against the average connectivity. (Below) Mean colors detected in connectivity intervals. (c) (Top) Settling time plotted against the average connectivity. (Below) Mean settling time in connectivity intervals. (d) Number of colors detected using the relaxation oscillator circuit plotted against number of colors detected using Brelaz heuristics for the random graph instances used in b and c. Each graph instance represents a point whose coordinates are denoted by the pair of colors detected using the two methods. The size of dots represents the percentage of instances which lie at the center of corresponding dot.