Mixed-Integer Linear Programming Model for the Super-Colored Path Problem in Digraphs

• Rafael Marian UFSC
• Wesly Carmesini Ataide UFSC
• Rafael de Santiago UFSC
• Álvaro Junio Pereira Franco UFSC

DOI: https://doi.org/10.5753/etc.2026.22099

Resumo

This paper presents a method based on Mixed-Integer Linear Programming (MILP) to solve the Super-Colored Path Problem. Given a digraph D with colored vertices, and for each vertex v in D, we want to find the maximum number of distinct colors that a simple path starting from v can take. The proposed method draws resemblance with the classic formulation for solving the Traveling Salesman Problem, in particular the presence of subtours.

Referências

Ataide, W. C., Santiago, R. d., and Franco, A. J. P. (2024). Algorithms for super-coloring in directed graphs. Proceedings of LVI Brazilian Symposium on Operations Research.

Dantzig, G., Fulkerson, R., and Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4):393–410.

Franco, Á. J. P. and Vendramin, M. E. (2021). Super-colored paths in digraphs. Anais do VI Encontro de Teoria da Computação, pages 94–97.

Franco, Á. J. P. and Vendramin, M. E. (2022). Uma experiência com redes de parentesco totalmente coloridas. In REACT – VIII Reunião de Antropologia da Ciência e da Tecnologia.

Gurski, F. (2015). Linear programming formulations for computing graph layout parameters. The Computer Journal, 58(11):2921–2927.

Miller, C. E., Tucker, A. W., and Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM, 7(4):326–329.

Vendramin, M. E. (2021). Algoritmos para encontrar anéis cromáticos em redes de parentesco. Trabalho de Conclusão de Curso.

Yao, L. (2023). Optimizing map coloring: Using linear programming to find the minimum number of colors. Theoretical and Natural Science, 28:1–9.