Name
Title | ||
|---|---|---|
Reachability and recurrence in a modular generalization of annihilating random walks (and lights-out games) to hypergraphs |
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 22] motivated by the statistical physics of social balance 3,2], generalizes certain lights-out games 31] to finite fields and also has some applications to the complexity of local search procedures 23].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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2015.02.035 | Theoretical Computer Science |
Keywords | DocType | Volume |
discrete complex systems,lights-out games,reachability | Journal | 580 |
Issue | ISSN | Citations |
C | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 4 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gabriel Istrate | 1 | 99 | 24.96 |
| C. Coposu | 2 | 0 | 0.34 |