Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds

Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model for the slime's behavior in the form of a coupled system of differential equations was proposed by Tero, Kobayashi and Nakagaki [TKN07]. We prove that a discretization of the model (Euler integration) computes a (1 + eps)-approximation of the shortest path in O( m L (logn + log L)/eps^3) iterations, with arithmetic on numbers of O(log(nL/eps)) bits; here, n and m are the number of nodes and edges of the graph, respectively, and L is the largest length of an edge. We also obtain two results for a directed Physarum model proposed by Ito et al. (2011): convergence in the general, nonuniform case and convergence and complexity bounds for the discretization of the uniform case.