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, 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 number of subdivisions needed for minimum stable divisorial gonality of a graph with n vertices is bounded by 2 p(n) for a polynomial p.
Original language | English |
---|---|
Title of host publication | SOFSEM 2019 |
Subtitle of host publication | Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings |
Editors | Barbara Catania, Giovanni Pighizzini, Rastislav Královič, Jerzy Nawrocki |
Place of Publication | Cham |
Publisher | Springer |
Pages | 81-93 |
Number of pages | 13 |
ISBN (Electronic) | 978-3-030-10801-4 |
ISBN (Print) | 978-3-030-10800-7 |
DOIs | |
Publication status | Published - 11 Jan 2019 |
Event | 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Nový Smokovec, Slovakia Duration: 27 Jan 2019 → 30 Jan 2019 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 11376 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 |
---|---|
Country/Territory | Slovakia |
City | Nový Smokovec |
Period | 27/01/19 → 30/01/19 |
Funding
H. L. Bodlaender—This work was supported by the NETWORKS project, funded by the Netherlands Organization for Scientific Research NWO under project no. 024.002.003.