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

Arnab Kole () and Anindya Jyoti Pal ()
Additional contact information
Arnab Kole: The Heritage Academy
Anindya Jyoti Pal: The University of Burdwan

Journal of Heuristics, 2025, vol. 31, issue 3, No 4, 44 pages

Abstract: Abstract 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.

Keywords: Ant Colony Optimization; Combinatorial Optimization; Graph Coloring; Hybridization; NP-Complete; Quantum Annealing (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09565-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:3:d:10.1007_s10732-025-09565-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09565-2

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().