Stable divisorial gonality is in NP
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)}\).
- A combinatorial Li-Yau inequality and rational points on curves
- Chip-firing games, potential theory on graphs, and spanning trees
- Computing graph gonality is hard
- Divisors and sandpiles. An introduction to chip-firing
- Gonality of algebraic curves and graphs
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- On the complexity of integer programming
- Recognizing hyperelliptic graphs in polynomial time
- Riemann-Roch and Abel-Jacobi theory on a finite graph
- Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
- Stable divisorial gonality is in NP
- Treewidth is a lower bound on graph gonality
This page was built for publication: Stable divisorial gonality is in NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918307)
