|
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-\epsilon} n})$ for any $\epsilon>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-\epsilon})$ for any $\epsilon>0$.
Bibtex entry:
| AUTHOR | = | {B{\'e}rczi, Krist{\'o}f and Hoang P., Hung and T{\'o}thm{\'e}r{\'e}sz, Lilla}, |
| TITLE | = | {On approximating the rank of graph divisors}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2023}, |
| NUMBER | = | {TR-2023-04} |