TR-2014-07

Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph

Viktor Kiss, Lilla Tóthmérész



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.
 

Previous versions can be found here and here.


Bibtex entry:

@techreport{egres-14-07,
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}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!