Aplicação de Algoritmos Combinatórios para o Problema do Caminho Tropical em Grafos

• Igor de M. Sampaio USP
• Karla R. P. S. Lima USP

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

Resumo

O problema do caminho tropical em grafos, TPP, consiste em, dado um grafo G e uma coloração dos vértices de G, encontrar um caminho colorido P em G em que cada cor usada por G apareça exatamente uma vez em P. Neste projeto propomos investigar duas versões de otimização desse problema: STPP, o problema do caminho tropical mínimo, que consiste em encontrar um caminho tropical de peso mínimo em que os pesos são atribuídos às arestas de G, e o MTPP, o problema do caminho tropical máximo, que consiste em encontrar o caminho com o maior número de cores usadas por G. É sabido que o problema é NP-difícil para grafos em geral e algumas outras variantes do problema. Do ponto de vista da combinatória poliédrica existem inúmeras técnicas de modelagem que permitem encontrar soluções ótimas para problemas dessa natureza em termos da complexidade computacional. Diante disso, o objetivo desse projeto é implementar uma boa formulação para o problema e associar algoritmos de alto desempenho para obtenção de soluções ótimas para instâncias de grande porte.

Palavras-chave: Otimização, Grafos, Algoritmos Combinatórios, Programação Linear Inteira, NP-Difícil

Referências

Bondy, J. A., Murty, U. S. R., et al. (1976). Graph theory with applications, volume 290. Macmillan London.

Cohen, J., Italiano, G. F., Manoussakis, Y., Thang, N. K., and Pham, H. P. (2019). Tropical paths in vertex-colored graphs. Journal of Combinatorial Optimization, pages 1–23.

Cohen, J., Manoussakis, Y., Phong, H., and Tuza, Z. (2017). Tropical matchings in vertex-colored graphs. Electronic Notes in Discrete Mathematics, 62:219–224.

Corel, E., Pitschi, F., and Morgenstern, B. (2010). A min-cut algorithm for the consistency problem in multiple sequence alignment. Bioinformatics, 26(8):1015–1021.

d’Auriac, J.-A. A., Bujtás, C., El Maftouhi, A., Karpinski, M., Manoussakis, Y., Montero, L., Narayanan, N., Rosaz, L., Thapper, J., and Tuza, Z. (2018). Tropical dominating sets in vertex-coloured graphs. Journal of Discrete Algorithms, 48:27–41.

Marx, D. (2004). Graph colouring problems and their applications in scheduling. Periodica Polytechnica Electrical Engineering, 48(1-2):11–16.

Sikora, F. (2012). An (almost complete) state of the art around the graph motif problem. Université Paris-Est Technical reports.

Uehara, R. and Uno, Y. (2004). Efficient algorithms for the longest path problem. In International symposium on algorithms and computation, pages 871–883. Springer.

West, D. B. et al. (2001). Introduction to Graph Theory, volume 2. Prentice hall Upper Saddle River.