We study the problem of computing the rank of a divisor on a finite graph, a quantity that arises in the Riemann-Roch theory on a finite graph developed by Baker and Norine (Advances of Mathematics, 215(2): 766-788, 2007). Our work consists of two parts: the first part is an algorithm whose running time is polynomial for a multigraph with a fixed number of vertices. More precisely, our algorithm has running time O(2^ n n )poly(size(G)), where n+1 is the number of vertices of the graph G. The second part consists of a new proof of the fact that testing if rank of a divisor is non-negative or not is in the complexity class NP intersection co-NP and motivated by this proof and its generalisations, we construct a new graph invariant that we call the critical automorphism group of the graph.
Our paper is centered around the problem of computing the rank. More precisely, (Section ) we obtain an algorithm whose running time is polynomial for a multigraph with a fixed number of vertices. More precisely, our algorithm has running time @math , where @math is the number of vertices of the multigraph @math . Recall that we are working with arbitrary undirected connected multigraphs or equivalently graphs with positive integer weights on the edges and indeed, the original Riemann-Roch theory was also developed in this setting. The main tools involved are the Riemann-Roch formula and a formula for rank (Theorem ) that is used in the proof of the Riemann-Roch formula, these results were first obtained in the work of Baker and Norine @cite_8 . We obtain a geometric interpretation of rank (Theorem ) and combine this geometric interpretation along with algorithms from the geometry of numbers to obtain the algorithm for computing the rank (Algorithm ). We find it satisfying that geometric tools seem to be essential in obtaining the algorithm, though the definition of rank of a divisor can be stated in purely combinatorial terms.
@cite_8
2083387674
Abstract It is well known that a finite graph can be viewed, in many respects, as a discrete analogue of a Riemann surface. In this paper, we pursue this analogy further in the context of linear equivalence of divisors. In particular, we formulate and prove a graph-theoretic analogue of the classical Riemann–Roch theorem. We also prove several results, analogous to classical facts about Riemann surfaces, concerning the Abel–Jacobi map from a graph to its Jacobian. As an application of our results, we characterize the existence or non-existence of a winning strategy for a certain chip-firing game played on the vertices of a graph.