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 -