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.
The central quantity in the Riemann-Roch theorem is the rank of a divisor and the efficient computation of rank is a natural problem, attributed to Hendrik Lenstra (see @cite_0 ). In fact this work, gave an algorithm, i.e., a procedure that terminates in a finite number of steps to compute the rank of a divisor on a tropical curve. But the algorithm does not run in polynomial time in the size of the multigraph even when the number of vertices are fixed since the algorithm involves iterating over all the spanning trees in the graph (see Proof of Theorem 23 in @cite_0 ) and the number of spanning trees in indeed not polynomially bounded in the size of the mutligraph even if the number of vertices are fixed. On the other hand, there are polynomial time algorithms for deciding if the rank of a divisor on a finite multigraph is non-negative, see @cite_2 , @cite_12 and @cite_5 .
@cite_0 @cite_5 @cite_12 @cite_2
2099082421 1818095014 2026915189
We investigate, using purely combinatorial methods, structural and algorithmic properties of linear equivalence classes of divisors on tropical curves. In particular, we confirm a conjecture of Baker asserting that the rank of a divisor D on a (non-metric) graph is equal to the rank of D on the corresponding metric graph, and construct an algorithm for computing the rank of a divisor on a tropical curve. Kirchhoff's matrix-tree theorem states that the number of spanning trees of a graph G is equal to the value of the determinant of the reduced Laplacian of @math . We outline an efficient bijective proof of this theorem, by studying a canonical finite abelian group attached to @math whose order is equal to the value of same matrix determinant. More specifically, we show how one can efficiently compute a bijection between the group elements and the spanning trees of the graph. The main ingredient for computing the bijection is an efficient algorithm for finding the unique @math -parking function (reduced divisor) in a linear equivalence class defined by a chip-firing game. We also give applications, including a new and completely algebraic algorithm for generating random spanning trees. Other applications include algorithms related to chip-firing games and sandpile group law, as well as certain algorithmic problems about the Riemann-Roch theory on graphs. Bjorner, Lvasz, and Shor have introduced a chip firing game on graphs. This paper proves a polynomial bound on the length of the game in terms of the number of vertices of the graph provided the length is finite. The obtained bound is best possible within a constant factor.