|
Baker and Norine introduced a graph-theoretic analogue of the Riemann-Roch theory.
A central notion in this theory is the rank of a divisor.
In this paper we prove that computing the rank of a divisor on a graph is NP-hard, even for simple graphs.
The determination of the rank of a divisor can be translated to a question about a
chip-firing game on the same underlying graph.
We prove the NP-hardness of this question by relating chip-firing on directed and undirected graphs.
Previous versions can be found here and here.
Bibtex entry:
| AUTHOR | = | {Kiss, Viktor and T{\'o}thm{\'e}r{\'e}sz, Lilla}, |
| TITLE | = | {Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2014}, |
| NUMBER | = | {TR-2014-07} |