Computing graph gonality is hard

DOI10.1016/J.DAM.2020.08.013MaRDI QIDQ2004086zbMATH OpenOpenAlexFDO

Authors Harry Smit, Marieke van der Wegen, Dion Gijswijt

Publication date 14 October 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

computational complexitytropical geometrygonalitychip-firing

Mathematics Subject Classification ID

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

Abstract: There are several notions of gonality for graphs. The divisorial gonality dgon(G) of a graph G is the smallest degree of a divisor of positive rank in the sense of Baker-Norine. The stable gonality sgon(G) of a graph G is the minimum degree of a finite harmonic morphism from a refinement of G to a tree, as defined by Cornelissen, Kato and Kool. We show that computing dgon(G) and sgon(G) are NP-hard by a reduction from the maximum independent set problem and the vertex cover problem, respectively. Both constructions show that computing gonality is moreover APX-hard.

Recommendations

• Stable divisorial gonality is in NP
• Stable divisorial gonality is in NP
• Stable gonality is computable
• Sparse graphs of high gonality
• On the scramble number of graphs

Cites work

• scientific article; zbMATH DE number 125906 (Why is no real title available?)
• A Spectral Lower Bound for the Divisorial Gonality of Metric Graphs
• A combinatorial Li-Yau inequality and rational points on curves
• 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
• 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 Magma algebra system. I: The user language
• The chip-firing game
• Treewidth is a lower bound on graph gonality
• Tropical hyperelliptic curves

Cited in

(17)

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

Describes a project that uses

Uses Software

• Magma

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)