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 consist 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 2p(n)
for a polynomial p.
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 consist 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 2p(n)
for a polynomial p.
Original language | English |
---|---|
Article number | 1808.06921 |
Number of pages | 15 |
Journal | CoRR |
Publication status | Published - 2018 |