Computing graph gonality is hard
The divisorial gonality of a graph \(G\), denoted by \(\operatorname{dgon}(G)\) is the smallest degree of a divisor of positive rank in the sense of \textit{M. Baker} and \textit{S. Norine} [Adv. Math. 215, No. 2, 766--788 (2007; Zbl 1124.05049)]. The stable gonality \(\operatorname{sgon}(G)\) of a graph \(G\) defined by \textit{G. Cornelissen} et al. [Math. Ann. 361, No. 1--2, 211--258 (2015; Zbl 1341.11034)] is the minimum degree of a finite harmonic morphism from a refinement of \(G\) to a tree. In this paper, it is shown, by a reduction from the maximum independent set problem and the vertex cover problem, respectively that computing \(\operatorname{dgon}(G)\) and \(\operatorname{sgon}(G)\) are NP-hard. Both constructions show that computing gonality is moreover APX-hard. The authors also show that divisorial and stable gonality are unbounded in one another.
- A combinatorial Li-Yau inequality and rational points on curves
- A Spectral Lower Bound for the Divisorial Gonality of Metric Graphs
- A tropical proof of the Brill-Noether theorem
- 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 graphs
- Chip-firing games, potential theory on graphs, and spanning trees
- Computational aspects of gonal maps and radical parametrization of curves
- Curves with infinitely many points of fixed degree
- Harmonic Morphisms and Hyperelliptic Graphs
- scientific article; zbMATH DE number 125906 (Why is no real title available?)
- Lifting harmonic morphisms. II: Tropical curves and metrized complexes
- Rank of divisors on tropical curves
- Recognizing hyperelliptic graphs in polynomial time
- Riemann-Roch and Abel-Jacobi theory on a finite graph
- Some APX-completeness results for cubic graphs
- Sparse graphs of high gonality
- Special divisors on marked chains of cycles
- Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
- Stable gonality is computable
- The chip-firing game
- The Magma algebra system. I: The user language
- Treewidth is a lower bound on graph gonality
- Tropical hyperelliptic curves
- A new lower bound on graph gonality
- On the scramble number of graphs
- Computing zeta functions of algebraic curves using Harvey's trace formula
- Discrete and metric divisorial gonality can be different
- Treewidth and gonality of glued grid graphs
- On the gonality of Cartesian products of graphs
- Gonality sequences of graphs
- Stable gonality is computable
- Recognizing hyperelliptic graphs in polynomial time
- Stable divisorial gonality is in NP
- Constructing tree decompositions of graphs with bounded gonality
- Stable divisorial gonality is in NP
- Recognizing hyperelliptic graphs in polynomial time
- Problems hard for treewidth but easy for stable gonality
- Multiplicity-free gonality on graphs
- On approximating the rank of graph divisors
- Graphs of scramble number two
- Fibonacci sumsets and the gonality of strip graphs
This page was built for publication: Computing graph gonality is hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2004086)
