Consensus on nonlinear spaces and graph coloring
Alain Sarlette · 2011
This paper comments on the complexity of equilibria reached by agents that evolve on a nonlinear space by interacting according to a fixed undirected graph. In particular, it considers agents on the projective space of ℝk, which links to the algorithmic problem of graph k-coloring. It is thereby shown that characterizing stable equilibria of repulsive agents on the projective space can be as difficult as graph coloring, that is NP-hard for k >; 2.