Print Email Facebook Twitter Computing graph gonality is hard Title Computing graph gonality is hard Author Gijswijt, Dion (TU Delft Discrete Mathematics and Optimization) Smit, Harry J. (Universiteit Utrecht) van der Wegen, Marieke (Universiteit Utrecht) Date 2020 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. Subject GonalityComputational complexityChip-firingGraph theoryTropical geometry To reference this document use: http://resolver.tudelft.nl/uuid:415dcfad-a7f2-4845-ac09-1b9a7d0cdc5c DOI https://doi.org/10.1016/j.dam.2020.08.013 ISSN 0166-218X Source Discrete Applied Mathematics, 287, 134-149 Part of collection Institutional Repository Document type journal article Rights © 2020 Dion Gijswijt, Harry J. Smit, Marieke van der Wegen Files PDF 1_s2.0_S0166218X20303796_main.pdf 587.45 KB Close viewer /islandora/object/uuid:415dcfad-a7f2-4845-ac09-1b9a7d0cdc5c/datastream/OBJ/view