Skip to content
Conference

Graph-Aware Large Language Models for Combinatorial Optimization

Aug 2026 · 2026 International Conference on Emerging Techniques in Computational Intelligence (ICETCI) · pp. 1-8 · 0 citations · 39 references

Abstract

This work proposes graph-aware hybrid approach that combines classical graph algorithms and Large Language Models (LLMs) to improve interpretability of the solutions for combinatorial optimization problems. The proposed framework is capable of solving such NP-hard problems as Traveling Salesman Problem (TSP), Graph Coloring, Maximum Clique, Minimum Vertex Cover and Hamiltonian Path using the optimization backend built with the use of FastAPI framework together with the LLM explanations and D3.js visualization. The proposed framework is evaluated using the datasets of TSPLIB, DIMACS and randomly generated graphs. The experimental results showed that TSP solver was able to find the solution that is 5.4% -14.5% far from the optimal tour length after 2-opt refinement, graph coloring is optimal in 4 out of 5 benchmarks and maximum clique is optimal in all evaluated datasets. Finally, the user experiment showed that LLM explanations can improve users' comprehension of the solutions without compromising the quality of the solutions.

View source

Similar papers

Review Open access Sep 2026

A New Metaheuristic Algorithm for Large Graph Coloring Problems

This is the first study to employ an ensemble-based approach that combines multiple metaheuristics for solving the GCP in a parallel computing environment, and demonstrates substantial reductions in execution time, with near-linear scalability and speed-up.

Tansel Dokeroglu, Deniz Canturk · 0 citations
Preprint Oct 2026

Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs

The Double-Partition Coloring Problem (DPCP) is a recently introduced generalization of several coloring problems on graphs and hypergraphs, including the Partition Coloring Problem, the List Coloring Problem, and the Conflict-Free Coloring Problem (CFCP). In this work, we further investigate the structural and computa...

Mauro Lucci, G. Nasini, Paola B. Tolomei et al. · 0 citations
Preprint Oct 2026

Solving problems in RDV Graphs faster and easier

In interval graphs and many generalizations thereof, problems such as Matching, Independent Set, and Dominating Set can be solved with simple greedy algorithms in linear (i.e., $O(m+n)$) time. However, it is sometimes possible to improve on this runtime if a suitable representation as intersection graph is given; for e...

T. Biedl, G. Rote · 0 citations

Dual-GNN Multilevel Coarsening for Maximum Independent Set

The Dual-GNN Multilevel Coarsening framework uses learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making and achieves the best mean solution quality among all evaluated methods.

Tian-Feng Chen, Xian-Yue Li · 0 citations

One Color Preprocessing Improves DSATUR

The Graph Coloring Problem (GCP) is NP-hard and DSATUR stands as one of the fastest heuristics for it despite producing colorings that typically use more colors than state-of-the-art coloring algorithms. We propose SSLD (Semidefinite Spectral Learning with DSATUR), which improves DSATUR by preprocessing a first good co...

A. Nouira, Lucas Isenmann · 0 citations
Preprint Nov 2026

Quantum-Informed Graph Decomposition

The Quantum Approximate Optimization Algorithm (QAOA) is a near-term quantum algorithm for solving combinatorial optimization problems, but its accuracy and resource requirements may scale poorly with problem size or structure, reducing its utility in practice. Approaches such as the Graph Decomposition for Optimizatio...

M. Brunet, Leah Prepchuk, Rebekah Herrman · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.