New Insights on Prize Collecting Path Problems - Santos, Edcarllos; Candia-Véjar, Alfredo; Ochi, Luiz Satoru; Simonetti, Luidi; Souza, Uéverton S. (Anais do Encontro de Teoria da Computação (ETC), 2017)
Given a graph G and a pair s,t in V(G), where each edge e has a weight t(e) and each vertex v has a value p(v) such that t(e) represent a transportation time and p(v) a prize collecting. Prize Collecting Path (PCP) consists of finding a (s,t)-path that minimizes the total transportation time minus the total prize of nodes in such path. PCP is at core of numerous relevant applications in several fields like telecommunications, transportation and logistics. In this paper, the complexity behavior of the problem is analyzed. For some cases we prove that PCP is NP-complete, these results lead to the generation of new sets of benchmark instances that are computationally hard according to natural characteristics of the problem. In addition, polynomial time algorithms are described for other cases and a mathematical formulation is introduced to solve general instances of PCP.