Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418845 | Discrete Applied Mathematics | 2015 | 9 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Viktor Kiss, Lilla Tóthmérész,