Computing graph gonality is hard
Publication date
2020-12-15
Authors
Gijswijt, Dion
Smit, Harry
Wegen, Marieke van der
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
cc_by
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.
Keywords
Chip-firing, Computational complexity, Gonality, Graph theory, Tropical geometry, Discrete Mathematics and Combinatorics, Applied Mathematics
Citation
Gijswijt, D, Smit, H & van der Wegen, M 2020, 'Computing graph gonality is hard', Discrete Applied Mathematics, vol. 287, pp. 134-149. https://doi.org/10.1016/j.dam.2020.08.013