Abstract
The development of tools based on robust mathematical models to deal with real-world, computationally intractable problems has increasingly aligned with combinatorial optimization and integer linear programming techniques due to enormous technological advances and the real need to deal with large volumes of data. In this paper, the Maximum Tropical Path Problem on graphs (MTPP), which is known to be NP-hard, was investigated. It is a problem of searching for specific structural patterns in networks that can represent various applications, among them biological interactions, such as metabolic, neurological or protein interaction networks. The main result of this work consists of a polynomial-time heuristic algorithm that, according to experimental results, finds good solutions in practice. Furthermore, an integer linear programming model was developed and implemented so that it could be compared with the heuristic presented. To conclude, an empirical analysis was performed through computational experiments on both random and real-word instances to evaluate the results presented in this paper.
This work was partially supported by grant 2021/07080-6, São Paulo Research Foundation (FAPESP) and by the Graduate Support Program (Proap)-CAPES.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Anglès d’Auriac, J.A., et al.: Tropical dominating sets in vertex-coloured graphs. J. Disc. Algor. 48, 27–41 (2018). https://doi.org/10.1016/j.jda.2018.03.001. https://www.sciencedirect.com/science/article/pii/S1570866718300595
Chapelle, M., Cochefert, M., Kratsch, D., Letourneur, R., Liedloff, M.: Exact exponential algorithms to find tropical connected sets of minimum size. Theor. Comput. Sci. 676, 33–41 (2017). https://doi.org/10.1016/j.tcs.2017.03.003. https://www.sciencedirect.com/science/article/pii/S0304397517301883
Cohen, J., Manoussakis, Y., Phong, H., Tuza, Z.: Tropical matchings in vertex-colored graphs. Electron. Notes Disc. Math. 62, 219–224 (2017). https://doi.org/10.1016/j.endm.2017.10.038, https://www.sciencedirect.com/science/article/pii/S1571065317302779
Cohen, J., Italiano, G.F., Manoussakis, Y., Nguyen, K.T., Pham, H.P.: Tropical paths in vertex-colored graphs. In: Gao, X., Du, H., Han, M. (eds.) COCOA 2017. LNCS, vol. 10628, pp. 291–305. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71147-8_20
Deville, Y., Gilbert, D.R., van Helden, J., Wodak, S.J.: An overview of data models for the analysis of biochemical pathways. Brief. Bioinf. 4(3), 246–259 (2003). https://doi.org/10.1093/bib/4.3.246
Foucaud, F., Harutyunyan, A., Hell, P., Legay, S., Manoussakis, Y., Naserasr, R.: The complexity of tropical graph homomorphisms. Disc. Appl. Math. 229(C), 64–81 (2017). https://doi.org/10.1016/j.dam.2017.04.027
Gabow, H.N., Nie, S.: Finding a long directed cycle. ACM Trans. Algor. (TALG) 4(1), 1–21 (2008)
Gephi: Conjuntos de dados gephi (2009). https://github.com/gephi/gephi/wiki/Datasets. Accessed 27 Sept 2021
Kelley, B.P., et al.: Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc. Natl. Acad. Sci. 100(20), 11394–11399 (2003). https://doi.org/10.1073/pnas.1534710100. https://www.pnas.org/content/100/20/11394
Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif search in graphs: application to metabolic networks. IEEE/ACM Trans. Comput. Biol. Bioinf. 3(4), 360–368 (2006). http://doi.ieeecomputersociety.org/10.1109/TCBB.2006.55
Markov, M., Ionut Andreica, M., Manev, K., Tapus, N.: A linear time algorithm for computing longest paths in cactus graphs. Serdica J. Comput. 6(3), 287p–298p (2012)
Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM (JACM) 7(4), 326–329 (1960)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Sampaio, I.M., Lima, K.R.P.S. (2023). A Combinatorial Optimization Model and Polynomial Time Heuristic for a Problem of Finding Specific Structural Patterns in Networks. In: Naldi, M.C., Bianchi, R.A.C. (eds) Intelligent Systems. BRACIS 2023. Lecture Notes in Computer Science(), vol 14195. Springer, Cham. https://doi.org/10.1007/978-3-031-45368-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-45368-7_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-45367-0
Online ISBN: 978-3-031-45368-7
eBook Packages: Computer ScienceComputer Science (R0)