{
  "id": "2206.09662",
  "version": "v1",
  "published": "2022-06-20T09:09:07.000Z",
  "updated": "2022-06-20T09:09:07.000Z",
  "title": "On approximating the rank of graph divisors",
  "authors": [
    "Kristóf Bérczi",
    "Hung P. Hoang",
    "Lilla Tóthmérész"
  ],
  "comment": "11 pages, 3 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Baker and Norine initiated the study of graph divisors as a graph-theoretic analogue of the Riemann-Roch theory for Riemann surfaces. One of the key concepts of graph divisor theory is the {\\it rank} of a divisor on a graph. The importance of the rank is well illustrated by Baker's {\\it Specialization lemma}, stating that the dimension of a linear system can only go up under specialization from curves to graphs, leading to a fruitful interaction between divisors on graphs and curves. Due to its decisive role, determining the rank is a central problem in graph divisor theory. Kiss and T\\'othm\\'eresz reformulated the problem using chip-firing games, and showed that computing the rank of a divisor on a graph is NP-hard via reduction from the Minimum Feedback Arc Set problem. In this paper, we strengthen their result by establishing a connection between chip-firing games and the Minimum Target Set Selection problem. As a corollary, we show that the rank is difficult to approximate to within a factor of $O(2^{\\log^{1-\\varepsilon}n})$ for any $\\varepsilon > 0$ unless $P=NP$. Furthermore, assuming the Planted Dense Subgraph Conjecture, the rank is difficult to approximate to within a factor of $O(n^{1/4-\\varepsilon})$ for any $\\varepsilon>0$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-06-20T09:09:07.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "graph divisor theory",
      "minimum feedback arc set problem",
      "minimum target set selection problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}