{
  "id": "1111.7251",
  "version": "v1",
  "published": "2011-11-30T17:54:07.000Z",
  "updated": "2011-11-30T17:54:07.000Z",
  "title": "The rank of a divisor on a finite graph: geometry and computation",
  "authors": [
    "Madhusudan Manjunath"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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 \\log 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-11-30T17:54:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05Exx"
    ],
    "keywords": [
      "finite graph",
      "complexity class np intersection co-np",
      "computation",
      "second part consists",
      "running time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1111.7251M"
    }
  }
}