On approximating the rank of graph divisors

DOI10.1016/J.DISC.2023.113528zbMATH Open1516.05141arXiv2206.09662MaRDI QIDQ6098103FDOQ6098103

Hung P. Hoang, Lilla Tóthmérész, Kristóf Bérczi

Publication date: 12 June 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

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^{lo{g}^{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$.

Full work available at URL: https://arxiv.org/abs/2206.09662

zbMATH Keywords

approximationchip-firingRiemann-Roch theorygraph divisorsminimum target set selection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games on graphs (graph-theoretic aspects) (05C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Riemann surfaces; Weierstrass points; gap sequences (14H55) Games involving graphs (91A43)

Cites Work

• Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
• Chip-firing and the critical group of a graph
• Chip-firing games, potential theory on graphs, and spanning trees
• Riemann-Roch for sub-lattices of the root lattice \(A_n\)
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Title not available (Why is that?)
• Chip-firing games on graphs
• A Riemann-Roch theorem in tropical geometry
• Title not available (Why is that?)
• Rank-determining sets of metric graphs
• Chip-firing games on directed graphs
• Rank of divisors on tropical curves
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
• Polynomial Bound for a Chip Firing Game on Graphs
• On Approximating Target Set Selection
• Target set selection for conservative populations
• Unique key Horn functions

   Recommendations

• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph 👍 👎
• On computation of Baker and Norine's rank on complete graphs 👍 👎
• Rank-determining sets of metric graphs 👍 👎
• Computing graph gonality is hard 👍 👎
• Rank of divisors on tropical curves 👍 👎

This page was built for publication: On approximating the rank of graph divisors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098103)