HOW FAR IS IT TO THE NEXT RECURRENT CONFIGURATION? AN NP-COMPLETE PROBLEM IN THE SANDPILE MODEL
Abstract
We take a look at transient configurations of the Abelian Sandpile Model (ASM). If we add enough grains on the "right" sites to this configuration we get a recurrent configuration of the ASM. In this paper we show that it is NP-complete to decide for a transient configuration c on a grid of size m × m and a natural number k if it is possible to add k grains of sand to c such that we get a recurrent configuration. We show this by reducing the problem of deciding whether a given planar cubic graph of size n ∈ Θ(m) has a vertex cover, which is NP-complete, to this problem.
References
- Discrete Mathematics 257, 341 (2002), DOI: 10.1016/S0012-365X(02)00434-X. Crossref, ISI, Google Scholar
- Phys. Rev. Lett. 59, 381 (1987), DOI: 10.1103/PhysRevLett.59.381. Crossref, ISI, Google Scholar
- Physica A: Statistical and Theoretical Physics 185, 129 (1992). Crossref, ISI, Google Scholar
- Phys. Rev. Lett. 64, 1613 (1990), DOI: 10.1103/PhysRevLett.64.1613. Crossref, ISI, Google Scholar
- Algorithmica 16, 4 (1996), DOI: 10.1007/BF02086606. Crossref, ISI, Google Scholar
- J. Comb. Theory, Ser. B 82, 102 (2001), DOI: 10.1006/jctb.2000.2026. Crossref, ISI, Google Scholar
M. Schulz , Measures for Transient Configurations of the Sandpile-Model, In: ACRI, 2006 (2006) pp. 238–247. Google Scholar- Complex Systems 17, 17 (2007). Google Scholar


