Continuous-time dynamics for solving NP-hard problems on graphs

In this talk we explore an unexpected connection between discrete optimisation and continuous-time dynamical systems on graphs. Specifically, we study the problem of finding the maximum clique in a fixed network (equivalently, the maximum independent set in its complement). This problem is NP-hard, and many heuristic algorithms have been proposed to address it.
The surprising twist is that, under certain constraints, the solution to this discrete optimisation problem can be inferred from the long-term behaviour of interacting biological species governed by a Lotka–Volterra system on the same network. Moreover, we observe that the quality of these solutions improves as the competitive pressure in the system is gradually increased. We explain this phenomenon by analysing a cascade of bifurcation points in the dynamics. We will also highlight a connection to Katz centrality and discuss a possible extension to hypergraphs.
As an additional result, we examine the first bifurcation in the cascade, which has a biologically meaningful interpretation. By deriving lower and upper bounds for this bifurcation point, we challenge the classical diversity–stability paradox in ecology, which claims that “large systems must be unstable.” Our refinement shows instead that instability is driven by high-degree outlier nodes rather than by the sheer number of species.
 

Join at imt.lu/sagrestia