Chip-firing

From Egres Open
Jump to: navigation, search

Problems in this category


Introduction

Chip-firing is a solitary game on a directed graph, defined by Björner, Lovász and Shor [1], [2]. In this game we consider a digraph [math]G[/math] with a pile of chips on each of its nodes. A position of the game, called a chip-distribution is described by a vector [math]x \in \mathbb{Z}^V[/math], where [math]x(v)[/math] denotes the number of chips on vertex [math]v \in V[/math]. The basic move of the game is firing a vertex. It means that this vertex passes a chip to its neighbors along each outgoing edge, and so its number of chips decreases by its outdegree. In other words, firing a vertex [math]v[/math] means taking the new chip-distribution [math]x - L_G \mathbf{1}_v[/math] instead of [math]x[/math]; where [math]L_G[/math] denotes the Laplacian matrix of [math]G[/math].

The firing of a vertex [math]v \in V[/math] is legal with respect to a distribution [math]x[/math], if [math]v[/math] has a nonnegative amount of chips after the firing. A legal game is a sequence of distributions in which every distribution is obtained from the previous one by a legal firing.

Björner, Lovász and Shor proved the Abelian property of the chip-firing game [1]. The Abelian sandpile model is closely related to chip-firing games.

Halting problem

Let us call a chip-distribution [math]x[/math] terminating, if every legal chip-firing game played starting from [math]x[/math] terminates, and call it non-terminating, if every legal chip-firing game played starting from [math]x[/math] can be continued indefinitely. According to the Abelian property of the chip-firing game, a chip-distribution is either terminating or non-terminating.

While in the case of simple undirected graphs, a terminating chip-firing game cannot last for more than [math]O(n^4)[/math] firings [3]; for digraphs and multigraphs, the number of firings in a terminating chip-firing game is not necessarily polynomial. Therefore, it is a natural question whether there exists a polynomial algorithm deciding that a chip-distribution [math]x[/math] is terminating or not. This is called the chip-firing halting problem.

Complexity of the halting problem
Eulerian Digraph General Directed Graph
Simple graph in P [2] Conjecture: NP-hard
Multigraph Conjecture: P [4] NP-complete[5]

Reachability problem

The chip-firing reachability problem is the following: Given two chip-distributions [math]x[/math] and [math]y[/math], decide whether there exists a legal game transforming [math]x[/math] to [math]y[/math]. If [math]y[/math] is reachable from [math]x[/math] by a legal game, we denote it by [math]x\leadsto y[/math].

While the reachability problem is known to be in P for Eulerian digraphs [2],[4], its complexity is open for non-Eulerian digraphs.

The chip-firing reachability problem is a special case of the reachability problem for integral vector addition systems.


Complexity of the reachability problem
Eulerian Digraph General Directed Graph
Simple graph in P [2] Conjecture: co-NP-hard
Multigraph in P [4] Conjecture: co-NP-hard

Graph divisor theory

In 2007, Baker and Norine proved a graph-theoretic analogue of the classical Riemann-Roch theorem for algebraic curves [6]. This result inspired much research about Riemann-Roch theorems on tropical curves, lattices and directed graphs, and gave rise to a new field usually called as graph divisor theory. As pointed out already in [6], graph divisor theory has a strong connection to chip-firing games.

Some important notions of graph divisor theory are: Linear equivalence of graph divisors, Picard group, Rank of graph divisors, Divisorial gonality of a graph, Reduced graph divisors.

Combinatorial open problems include finding Upper bound on the divisorial gonality of a graph, Complexity of computing a v-reduced divisor in multigraphs.

Rotor-routing

Rotor routing is played on a ribbon digraph. A ribbon digraph is a digraph, where for each vertex, the out-edges from that vertex have a fixed cyclic order. A rotor-configuration is a mapping, that assigns an outgoing edge (the rotor edge) to each vertex. A chip-and-rotor configuration is a chip-distribution together with a rotor-configuration.

The rotor-routing game proceeds as follows: A vertex can be routed if it has a positive number of chips. If a vertex is routed, the rotor edge of the vertex is augmented to the next edge in the cyclic order, and a chip is taken from the vertex, and is placed on the head of the new rotor edge.

Holroyd et. al [7] defined a group action of the picard group on the set of spanning in-arborescences of a graph with the help of rotor-routing. The computation of this group action is open.

References

  1. 1.0 1.1 A. Björner, L. Lovász, P. Shor, Chip-firing games on graphs, Eur. J. Comb. (1991) DOI link, Author link
  2. 2.0 2.1 2.2 2.3 A. Björner, L. Lovász, Chip-firing games on directed graphs, J. Algebraic Comb. (1992) DOI link, Author link
  3. G. Tardos, Polynomial bound for a chip firing game on graphs, SIAM J. Discret. Math. (1988) DOI link,
  4. 4.0 4.1 4.2 B. Hujter, V. Kiss, L. Tóthmérész, On the complexity of the chip-firing reachability problem, EGRES Technical Report
  5. M. Farrell, L. Levine, Coeulerian graphs, Proc. AMS (2016) DOI link, ArXiv link
  6. 6.0 6.1 M. Baker, S. Norine, Riemann--Roch and Abel--Jacobi theory on a finite graph, Advances in Mathematics (2007) DOI link, ArXiv Link
  7. A. E. Holroyd, L. Levine, K. Mészáros, Y. Peres, J. Propp, D. B. Wilson, Chip-Firing and Rotor-Routing on Directed Graphs, Progress in Probability (2008) DOI link, Author Link