On approximating the rank of graph divisors

Bérczi, Kristóf and Hoang, Hung P. and Tóthmérész, Lilla (2023) On approximating the rank of graph divisors. DISCRETE MATHEMATICS, 346 (9). ISSN 0012-365X

Preview

Text 2206.09662.pdf Download (584kB) | Preview

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 rank of a divisor on a graph. The importance of the rank is well illustrated by Baker’s 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(2log1−ε n) for any ε > 0 unless P = N P . Furthermore, assuming the Planted Dense Subgraph Conjecture, the rank is difficult to approximate to within a factor of O(n1/4−ε) for any ε > 0.

Actions (login required)

Edit Item