A Combinatorial Optimization Model and Polynomial Time Heuristic for a Problem of Finding Specific Structural Patterns in Networks

• Igor M. Sampaio USP https://orcid.org/0000-0002-0929-4733
• Karla Roberta P. S. Lima USP https://orcid.org/0000-0001-5483-5466

Resumo

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.