Computing graph gonality is hard

DOI10.1016/j.dam.2020.08.013zbMath1450.05088arXiv1504.06713OpenAlexW3080153597MaRDI QIDQ2004086

Harry Smit, Marieke van der Wegen, Dion C. Gijswijt

Publication date: 14 October 2020

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

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

zbMATH Keywords

computational complexitygonalitytropical geometrychip-firing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Discrete and metric divisorial gonality can be different ⋮ Problems hard for treewidth but easy for stable gonality ⋮ Multiplicity-free gonality on graphs ⋮ Graphs of scramble number two ⋮ On the gonality of Cartesian products of graphs ⋮ Recognizing hyperelliptic graphs in polynomial time ⋮ Constructing tree decompositions of graphs with bounded gonality ⋮ Stable divisorial gonality is in NP ⋮ A new lower bound on graph gonality ⋮ Gonality Sequences of Graphs ⋮ On the scramble number of graphs ⋮ Computing zeta functions of algebraic curves using Harvey's trace formula

Uses Software

• Magma

Cites Work

• Unnamed Item
• Computational aspects of gonal maps and radical parametrization of curves
• A tropical proof of the Brill-Noether theorem
• Chip-firing games on graphs
• Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
• Chip-firing and the critical group of a graph
• Curves with infinitely many points of fixed degree
• The Magma algebra system. I: The user language
• Some APX-completeness results for cubic graphs
• Chip-firing games, potential theory on graphs, and spanning trees
• Tropical hyperelliptic curves
• Lifting harmonic morphisms. II: Tropical curves and metrized complexes
• Treewidth is a lower bound on graph gonality
• A combinatorial Li-Yau inequality and rational points on curves
• 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
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Special divisors on marked chains of cycles
• The chip-firing game
• Harmonic Morphisms and Hyperelliptic Graphs
• A Spectral Lower Bound for the Divisorial Gonality of Metric Graphs
• Sparse Graphs of High Gonality
• Stable gonality is computable
• Recognizing hyperelliptic graphs in polynomial time

This page was built for publication: Computing graph gonality is hard