Computing graph gonality is hard
From MaRDI portal
Publication:2004086
DOI10.1016/J.DAM.2020.08.013zbMATH Open1450.05088arXiv1504.06713OpenAlexW3080153597MaRDI QIDQ2004086FDOQ2004086
Harry Smit, Marieke van der Wegen, Dion Gijswijt
Publication date: 14 October 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1504.06713
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- The Magma algebra system. I: The user language
- Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
- Tropical hyperelliptic curves
- Chip-firing and the critical group of a graph
- Some APX-completeness results for cubic graphs
- Chip-firing games, potential theory on graphs, and spanning trees
- Riemann-Roch and Abel-Jacobi theory on a finite graph
- Chip-firing games on graphs
- Lifting harmonic morphisms. II: Tropical curves and metrized complexes
- The chip-firing game
- Harmonic Morphisms and Hyperelliptic Graphs
- A tropical proof of the Brill-Noether theorem
- Curves with infinitely many points of fixed degree
- Computational aspects of gonal maps and radical parametrization of curves
- Rank of divisors on tropical curves
- Sparse Graphs of High Gonality
- Recognizing hyperelliptic graphs in polynomial time
- Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
- Special divisors on marked chains of cycles
- A combinatorial Li-Yau inequality and rational points on curves
- A Spectral Lower Bound for the Divisorial Gonality of Metric Graphs
- Treewidth is a lower bound on graph gonality
- Stable gonality is computable
Cited In (12)
- Constructing tree decompositions of graphs with bounded gonality
- Computing zeta functions of algebraic curves using Harvey's trace formula
- On the gonality of Cartesian products of graphs
- Gonality Sequences of Graphs
- Discrete and metric divisorial gonality can be different
- Graphs of scramble number two
- Problems hard for treewidth but easy for stable gonality
- Multiplicity-free gonality on graphs
- On the scramble number of graphs
- A new lower bound on graph gonality
- Recognizing hyperelliptic graphs in polynomial time
- Stable divisorial gonality is in NP
Uses Software
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)
