Stable Divisorial Gonality is in NP
- PDF / 359,028 Bytes
- 13 Pages / 439.642 x 666.49 pts Page_size
- 42 Downloads / 158 Views
Stable Divisorial Gonality is in NP Hans L. Bodlaender1 · Marieke van der Wegen1
· Tom C. van der Zanden2
Accepted: 12 November 2020 © The Author(s) 2020
Abstract Divisorial gonality and stable divisorial gonality are graph parameters, which have an origin in algebraic geometry. Divisorial gonality of a connected graph G can be defined with help of a chip firing game on G. The stable divisorial gonality of G is the minimum divisorial gonality over all subdivisions of edges of G. In this paper we 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 by Gijswijt et al., we 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, we have that the total number of subdivisions needed for minimum stable divisorial gonality of a graph with m edges is bounded by mO(mn) . Keywords Computational complexity · Graphs · Gonality
1 Introduction The notions of the divisorial gonality and stable divisorial gonality of a graph find their origin in algebraic geometry and are related to the abelian sandpile model (cf. Hans L. Bodlaender was partially supported by the Networks project, founded by the Dutch Organization for Scientific Research NWO, while partly associated to the Department of Mathematics and Computer Science at Eindhoven University of Technology. This work was done while Tom C. van der Zanden is associated with the Department of Information and Computing Sciences of Utrecht University. An extended abstract is published in SOFSEM 2019: Theory and Practice of Computer Science [1]. Marieke van der Wegen
[email protected] 1
Department of Information and Computing Sciences, Universiteit Utrecht, Princetonplein 5, 3584 CC Utrecht, The Netherlands
2
Department of Data Analytics and Digitalisation, Maastricht University, Maastricht, The Netherlands
Theory of Computing Systems
[2]). Baker and Norine introduced divisor theory on graphs in [3]. The notion of divisorial gonality was introduced by Baker [4], under the name gonality. As there are several different notions of gonality in use (cf. [4–6]), we add the term divisorial, following [5]. See [6, Appendix A] for an overview of the different notions. 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 ∈ 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 neighbour 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 can be defined as the minimum number of chips in an initial assignment of chips (called divisor) such that for each vertex v ∈ V , there is a
Data Loading...
