Application of Combinatorial Algorithms for the Tropical Path Problem in Graphs

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

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

Abstract

The problem of the tropical path in graphs, TPP, consists of given a graph G and a coloring of the vertices of G, finding a colored path P in G where each color used by G appears exactly once in P. In this project we propose to investigate two versions of optimization of this problem: STTP, Shortest tropical path problem, that consists of finding a tropical path of minimum weight, such that the weights are assigned to the edges of G, and the MTPP, Maximum tropical problem path, that consists of finding the path with the largest number of colors used by G. It is known that the problem is NP-hard for graphs in general and some other variants of the problem. From the point of view of polyhedral combinatorics, there are numerous modeling techniques that allow to find optimal solutions to difficult problems in terms of computational complexity. Therefore, the objective of this project is to implement a good formulation for the problem and to associate it with high performance algorithms to obtain optimal solutions for large instances.

Keywords: Optimization, Graphs, Combinatorial Algorithms, Integer Linear Programming, NP-Hard

References

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.