×

Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph. (English) Zbl 1317.05122

Summary: M. Baker and S. Norine [Adv. Math. 215, No. 2, 766–788 (2007; Zbl 1124.05049)] 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.

MSC:

05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 1124.05049
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Amini, O.; Manjunath, M., Riemann-Roch for sub-lattices of the root lattice \(A_n\), Electron. J. Combin., 17, 1 (2010), Research Paper 124, 50 · Zbl 1277.05105
[3] Baker, M., Specialization of linear systems from curves to graphs, Algebra Number Theory, 2, 6, 613-653 (2008), With an appendix by Brian Conrad · Zbl 1162.14018
[4] Baker, M.; Norine, S., Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 2, 766-788 (2007) · Zbl 1124.05049
[5] Baker, M.; Shokrieh, F., Chip-firing games, potential theory on graphs, and spanning trees, J. Combin. Theory Ser. A, 120, 1, 164-182 (2013) · Zbl 1408.05089
[6] Björner, A.; Lovász, L., Chip-firing games on directed graphs, J. Algebraic Combin., 1, 4, 305-328 (1992) · Zbl 0805.90142
[7] Björner, A.; Lovász, L.; Shor, P. W., Chip-firing games on graphs, European J. Combin., 12, 4, 283-291 (1991) · Zbl 0729.05048
[9] Hladký, J.; Král’, D.; Norine, S., Rank of divisors on tropical curves, J. Combin. Theory Ser. A, 120, 7, 1521-1538 (2013) · Zbl 1317.14137
[10] Luo, Y., Rank-determining sets of metric graphs, J. Combin. Theory Ser. A, 118, 6, 1775-1793 (2011) · Zbl 1227.05133
[12] Perrot, K.; Van Pham, T., Feedback arc set problem and np-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs, Ann. Comb., 19, 1, 1-24 (2015) · Zbl 1331.68095
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.