Chip-firing

Problems in this category

• Complexity of computing a v-reduced divisor in multigraphs
• Complexity of computing the rotor-router action
• Complexity of the chip-firing reachability problem for general digraphs
• Complexity of the halting problem for Eulerian multigraphs
• Complexity of the halting problem for simple digraphs
• Gonality and edge subdivisions
• Rotor-routing halting problem
• Upper bound on the divisorial gonality of a graph

Introduction

Chip-firing is a solitary game on a directed graph, defined by Björner, Lovász and Shor , . 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 . 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 ; 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	Conjecture: NP-hard
Multigraph	Conjecture: P	NP-complete

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 ,, 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	Conjecture: co-NP-hard
Multigraph	in P	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 . 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 , 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 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.