On approximating the rank of graph divisors

DOI10.1016/J.DISC.2023.113528MaRDI QIDQ6098103zbMATH OpenFDO

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

Publication date 12 June 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• A Riemann-Roch theorem in tropical geometry
• Chip-firing and the critical group of a graph
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
• Chip-firing games on directed graphs
• Chip-firing games on graphs
• Chip-firing games, potential theory on graphs, and spanning trees
• On approximating target set selection
• Polynomial Bound for a Chip Firing Game on Graphs
• Rank of divisors on tropical curves
• Rank-determining sets of metric graphs
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Riemann-Roch for sub-lattices of the root lattice \(A_n\)
• Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
• Target set selection for conservative populations
• Tropical curves, their Jacobians and theta functions
• Unique key Horn functions

Cited in

(2)

• Stable divisorial gonality is in NP
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph

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)