On the Solution of the Steiner Tree NP-Hard Problem via Physarum BioNetwork

Abstract: In the last several years, many algorithms trying to mimic biological processes have been proposed to enhance the performance of communication networks. However, the bio-inspired algorithms represent only the very first step toward the design of a smart adaptive communication network since: 1) they model only a limited set of the rules underlying the biological processes, thus, omitting fundamental functionalities; 2) they are executed on traditional computer architectures, thus, failing to achieve the intrinsic parallelism exhibited by biological processes. To overcome these issues, in this paper, the BioNetwork paradigm is proposed, a novel communication network paradigm in which the traditional network nodes are replaced by living organisms. The BioNetwork paradigm provides very attractive features over traditional network paradigms, such as efficiency, adaptivity, reliability, self-organization, and scalability. Moreover, it has a huge potential since it can be adopted in many different applications, such as health and military ones. In the paper, this potential is shown by proving that a BioNetwork can solve one of the most fundamental NP-hard problems in networks, i.e., the Steiner tree problem. To this aim, a BioNetwork constituted by a unicellular organism, the Physarum polycephalum slime mold, is designed. Throughout the paper, it is proven that a Physarum BioNetwork can solve the Steiner tree problem with an exponential convergence rate toward the optimal solution. The theoretical solutions are validated through a case study.