April 16, 2014

Theory Lunch: Kurt Mehlhorn – January 11, 2013

Title: Physarum Computations
Speaker: Kurt Mehlhorn, Max Planck Institute for Informatics

[Complete Video]


Physarum is a slime mold. It was observed over the past 10 years that the mold is able to solve shortest path problems and to construct good Steiner networks (Nakagaki-Yamada-Toth,Tero-Takagi-etal). In a nutshell, the shortest path experiment is as follows: A maze is built and the mold is made to cover the entire maze. Food is then provided at two positions and and the evolution of the slime is observed. Over time, the slime retracts to the shortest path connecting the two food sources.

A video showing the wet-lab experiment can be found at http://www.youtube.com/watch?v=czk4xgdhdY4

A mathematical model of the slime’s dynamic behavior was proposed in 2007 by Tero-Kobayashi-Nakagaki. Extensive computer simulations of the mathematical model confirm the experimental findings. For the edges on the shortest path, the diameter converges to a fixed value, and for the edges off the shortest path, the diameter converges to zero.

We review the wet-lab and computer experiments and provide a proof for these experimental findings. We also suggest avenues for further work.

The talk is based on joint work with Vincenzo Bonifaci (Rome) and Girish Varma (TIFR).