RECORD
On approximating the rank of graph divisors
Combinatorics · Submitted 20 Jun 2022
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Baker and Norine initiated the study of graph divisors as a graph-theoretic analogue of the Riemann-Roch theory for Riemann surfaces. | background 1.00 | 0.03 | 0.01 | asserted 1.00 |
| s1 | One of the key concepts of graph divisor theory is the {\it rank} of a divisor on a graph. | background 1.00 | 0.04 | 0.01 | asserted 1.00 |
| s2 | 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. | background 1.00 | 0.03 | 0.02 | asserted 0.99 |
| s3 | Due to its decisive role, determining the rank is a central problem in graph divisor theory. | background 0.99 | 0.05 | 0.02 | asserted 1.00 |
| s4 | 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. | background 1.00 | 0.03 | 0.03 | asserted 1.00 |
| s5 | In this paper, we strengthen their result by establishing a connection between chip-firing games and the Minimum Target Set Selection problem. | contribution 0.99 | 0.92 | 0.10 | asserted 1.00 |
| s6 | 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$. | result 0.99 | 0.94 | 0.53 | asserted 1.00 |
| s7 | 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$. | result 0.99 | 0.85 | 0.20 | asserted 0.83 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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$.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 1 sentence without a confident label
Cites as background 2 papers
-
Lenstra, and was explicitly posed by many, see [ref] .
The rank of a divisor on a finite graph: geometry and computation · Introduction · 0.88
-
Cori and le Borgne [ref] provided a linear time algorithm for determining the rank of a divisor on a complete graph.
The Riemann-Roch theorem for graphs and the rank in complete graphs · Introduction · 0.87
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.