TY - GEN
T1 - Stable divisorial gonality is in NP
AU - Bodlaender, Hans L.
AU - van der Wegen, Marieke
AU - van der Zanden, Tom C.
PY - 2019/1/11
Y1 - 2019/1/11
N2 -
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.
AB -
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.
UR - http://www.scopus.com/inward/record.url?scp=85062362936&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-10801-4_8
DO - 10.1007/978-3-030-10801-4_8
M3 - Conference contribution
AN - SCOPUS:85062362936
SN - 978-3-030-10800-7
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 81
EP - 93
BT - SOFSEM 2019
A2 - Catania, Barbara
A2 - Pighizzini, Giovanni
A2 - Královič, Rastislav
A2 - Nawrocki, Jerzy
PB - Springer
CY - Cham
T2 - 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
Y2 - 27 January 2019 through 30 January 2019
ER -