{
  "id": "1312.3537",
  "version": "v2",
  "published": "2013-12-12T16:32:33.000Z",
  "updated": "2015-06-11T16:30:41.000Z",
  "title": "Computing the Tutte Polynomial of Lattice Path Matroids Using Determinantal Circuits",
  "authors": [
    "Jason Morton",
    "Jacob Turner"
  ],
  "categories": [
    "math.CO",
    "cs.CC"
  ],
  "abstract": "We give a quantum-inspired $O(n^4)$ algorithm computing the Tutte polynomial of a lattice path matroid, where $n$ is the size of the ground set of the matroid. Furthermore, this can be improved to $O(n^2)$ arithmetic operations if we evaluate the Tutte polynomial on a given input, fixing the values of the variables. The best existing algorithm, found in 2004, was $O(n^5)$, and the problem has only been known to be polynomial time since 2003. Conceptually, our algorithm embeds the computation in a determinant using a recently demonstrated equivalence of categories useful for counting problems such as those that appear in simulating quantum systems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-12-12T16:32:33.000Z",
      "abstract": "We give an $O(n^4)$ algorithm computing the Tutte polynomial of a lattice path matroid, where $n$ is the size of the ground set of the matroid. The best existing algorithm was $O(n^5)$. Furthermore, this can be improved to $O(n^2)$ if we evaluate the Tutte polynomial on a given input, fixing the values of the variables. Conceptually, our algorithm embeds the computation in a determinant using a recently demonstrated equivalence of categories useful for counting problems.",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-06-11T16:30:41.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "lattice path matroid",
      "tutte polynomial",
      "determinantal circuits",
      "ground set",
      "best existing algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1312.3537M"
    }
  }
}