Finding large independent sets in networks using competitive dynamics

Abstract

Many decision-making algorithms draw inspiration from the inner workings of individual biological systems. However, it remains unclear whether collective behaviour among biological species can also lead to solutions for computational tasks. By studying the coexistence of species that interact through simple rules on a network, we demonstrate that the underlying dynamical system can recover near-optimal solutions to the maximum independent set problem – a fundamental, computationally hard problem in graph theory. Furthermore, we observe that the optimality of these solutions is improved when the competitive pressure in the system is gradually increased. We explain this phenomenon by showing that the cascade of bifurcation points, which occurs with increasing competitive pressure in our dynamical system, naturally gives rise to Katz centrality-based node removal in the network. The results are relevant for biology, economics, and analogue computing.