On approximating the rank of graph divisors
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910405538873344 |
|---|---|
| author | Bérczi, Kristóf Hoang, Hung P. Tóthmérész, Lilla |
| author_facet | Bérczi, Kristóf Hoang, Hung P. Tóthmérész, Lilla |
| contents | 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óthméresz 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_09662 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On approximating the rank of graph divisors Bérczi, Kristóf Hoang, Hung P. Tóthmérész, Lilla Combinatorics Discrete Mathematics 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óthméresz 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$. |
| title | On approximating the rank of graph divisors |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2206.09662 |