Verifying the minimal cubic graph without Gallai vertice in parallel with code generated by LLM: An initial study

• Arthur H. D. Rodrigues USP
• Alfredo Goldman USP

DOI: https://doi.org/10.5753/eradsp.2026.31019

Resumo

A Gallai vertex in a graph is a vertex that belongs to all of its longest paths. In this paper, we study the implementation of a parallel algorithm to check if a given graph has a Gallai vertex. We implemented this algorithm purely with genAI and evaluated how well it could parallelize the algorithm using OpenMP. We confirmed a preexisting conjecture about the smallest cubic graph with no Gallai vertex and observed that genAI could implement and parallelize the algorithm in different granularities.

Referências

Chen, F. (2018). Order of the smallest counterexample to Gallai’s conjecture. Czechoslovak Mathematical Journal, 68(2):341–369.

Coolsaet, K., D’hondt, S., and Goedgebeur, J. (2023). House of graphs 2.0: a database of interesting graphs and more. Discrete Applied Mathematics, 325:57–65.

de Lazari Bento, H. (2026). Minimum longest path transversals in cubic graphs. Master thesis, University of São Paulo.

Fieger, K., Balyo, T., Schulz, C., and Schreiber, D. (2019). Finding optimal longest paths by dynamic programming in parallel. In Proceedings of the 12th Annual SoCS.