Stable divisorial gonality is in NP (Q5918307)

Divisorial gonality and stable divisorial gonality have definitions in terms of a chip-firing game. In this chip-firing game, played on a connected multigraph \(G = (V,E)\), each vertex has a number of chips. When we fire a vertex \(v\in V\), we move a chip from vertex \(v\) over each edge with \(v\) as endpoint. Vertex \(v\) has its number of chips decreased by the degree of \(v\), and each neighbor \(u\) of \(v\) has its number of chips increased by the number of edges from \(v\) to \(u\). The divisorial gonality of a connected graph \(G\) is defined as the minimum number of chips in an initial assignment of chips (called divisor) such that for each vertex \(v\in V\), there is a sequence of firing moves resulting in at least one chip on \(v\) and a non-negative number of chips on the other vertices. The stable divisorial gonality of a graph is a variant of the divisorial gonality, which is the minimum of the divisorial gonality over all subdivisions of a graph. In this paper the authors prove that deciding whether a given connected graph has stable divisorial gonality at most a given integer \(k\) belongs to the class NP. Combined with the result that (stable) divisorial gonality is NP-hard in [\textit{D. Gijswijt} et al., Discrete Appl. Math. 287, 134--149 (2020; Zbl 1450.05088)], the authors obtain that stable divisorial gonality is NP-complete. The proof consists of a partial certificate that can be verified by solving an Integer Linear Programming instance. As a corollary, they have that the total number of subdivisions needed for minimum stable divisorial gonality of a graph with \(m\) edges is bounded by \(m^{O(mn)}\).