Efficient Hybridization of Quantum Annealing and Ant Colony Optimization for Coloring DIMACS Graph Instances

Graph coloring problem is a well-known NP-complete combinatorial optimization problem where the goal is to assign colors to the vertices of a graph such that no adjacent vertices share the same color. Despite extensive research, no known polynomial-time algorithm exists for finding the optimal coloring for all the benchmark graph instances. This paper presents a time-efficient effective hybridization of ant colony optimization and quantum annealing algorithms in a single framework to solve graph coloring. The algorithm has been tested on 100 standard DIMACS benchmark graph instances of varying size and complexity. The experimental result shows that quantum annealing outperforms the performances of ant colony optimization in terms of obtaining the optimal/best-known chromatic number. However, the runtime of quantum annealing is too high for some simple graph instances of larger size. On the other hand, ant colony optimization gives faster result than quantum annealing for the simple graphs, but the performance is not satisfactory for some complex benchmark instances. The hybridization approach gives optimal/best-known results for the complex graphs and takes less time for the large-sized instances. By conducting a performance comparison among the individual algorithms with the hybridization using Friedman Test and Nemenyi Post-hoc analysis, the worthiness of the proposed hybrid algorithm is explained, establishing its promising nature.