Gabriel Istrate. Reachability and Recurrence in a Modular Generalization of Annihilating Random Walks (and lightsout games) to hypergraphs. Theoretical Computer Science , 580, pp. 8393, 2015.
Abstract:
We study a discrete asynchronous dynamical system on hypergraphs that can be regarded as a natural extension of annihilating walks along two directions: first, the interaction topology is a hypergraph; second, the number of particles at a vertex of the hypergraph is an element of a finite ring Z_p of integers modulo an odd number p>= 3. Equivalently, particles move on a hypergraph, with a moving particle at a vertex being replaced by one indistinguishable copy at each neighbor in a given hyperedge; particles at a vertex collectively annihilate when their number reaches p.
The boolean version of this system arose in earlier work motivated by our earlier work on the statistical physics of social balance, generalizes certain lightsout games to finite fields and also has some applications to the complexity of local search procedures.
Our result shows that under a liberal sufficient condition on the nature of the interaction hypergraph there exists a polynomial time algorithm (based on linear algebra over Z_p) for deciding reachability and recurrence of this dynamical system. Interestingly, we provide a counterexample that shows that this connection does not extend to all graphs.
For a preprint version see http://tcs.ieat.ro/wpcontent/uploads/2013/06/arxiv.pdf
Keywords:
discrete complex systems, ightsout games, reachability
URL:
http://www.sciencedirect.com/science/article/pii/S0304397515001711
Posted by
Gabriel Istrate
Back
