Energy function-based approaches to graph coloring

Area of Science:

• Artificial Intelligence
• Computational Complexity
• Network Science

Background:

• Optimization problems, such as graph coloring, are computationally challenging.
• Previous applications of Hopfield networks to graph coloring had limitations in encoding efficiency and neuron type.
• A need exists for more effective and compact neural network approaches for combinatorial optimization.

Purpose of the Study:

• To present a novel optimization framework based on a multiple-restart quasi-Hopfield network.
• To apply this framework to three distinct graph coloring problem variants.
• To demonstrate the advantages of k-state neurons over binary neurons in this context.

Main Methods:

• Developed a quasi-Hopfield network optimization approach.
• Embedded problem-specific knowledge solely within the energy function.
• Utilized k-state neurons for graph coloring, differing from prior binary neuron approaches.
• Applied the method to minimum coloring, spanning subgraph k-coloring, and induced subgraph k-coloring problems.

Main Results:

• The proposed k-state neuron encoding is more compact and natural than previous binary neuron methods.
• The new approach significantly reduces network connections asymptotically.
• It effectively avoids the issue of multiple colors assigned to a single vertex.
• Experimental results show favorable comparisons with existing graph coloring algorithms, including non-neural methods.

Conclusions:

• The quasi-Hopfield network with k-state neurons provides an effective and efficient method for graph coloring optimization.
• This approach offers a significant improvement over previous neural network applications in terms of encoding and problem handling.
• The framework demonstrates strong performance, comparable to specialized algorithms.