Computing graph gonality is hard (Q2004086)

The divisorial gonality of a graph \(G\), denoted by \(\operatorname{dgon}(G)\) is the smallest degree of a divisor of positive rank in the sense of \textit{M. Baker} and \textit{S. Norine} [Adv. Math. 215, No. 2, 766--788 (2007; Zbl 1124.05049)]. The stable gonality \(\operatorname{sgon}(G)\) of a graph \(G\) defined by \textit{G. Cornelissen} et al. [Math. Ann. 361, No. 1--2, 211--258 (2015; Zbl 1341.11034)] is the minimum degree of a finite harmonic morphism from a refinement of \(G\) to a tree. In this paper, it is shown, by a reduction from the maximum independent set problem and the vertex cover problem, respectively that computing \(\operatorname{dgon}(G)\) and \(\operatorname{sgon}(G)\) are NP-hard. Both constructions show that computing gonality is moreover APX-hard. The authors also show that divisorial and stable gonality are unbounded in one another.