Game of Life-like Opinion Dynamics: Generalizing the Underpopulation Rule

Graph dynamics for a node-labeled graph is a set of updating rules describing how the labels of each node in the graph change in time as a function of the global set of labels. The underpopulation rule is graph dynamics derived by simplifying the set of rules constituting the Game of Life. It is known that the number of label configurations met by a graph during the dynamic process defined by such rule is bounded by a polynomial in the size of the graph if the graph is undirected. As a consequence, predicting the labels evolution is an easy problem (i.e., a problem in P) in such a case. In this paper, the generalization of the underpopulation rule to signed and directed graphs is studied. It is here proved that the number of label configurations met by a graph during the dynamic process defined by any so generalized underpopulation rule is still bounded by a polynomial in the size of the graph if the graph is undirected and structurally balanced, while it is not bounded by any polynomial in the size of the graph if the graph is directed although unsigned unless P = PSpace.