TY - JOUR
T1 - Computing graph gonality is hard
AU - Gijswijt, Dion
AU - Smit, Harry
AU - van der Wegen, Marieke
PY - 2020/12/15
Y1 - 2020/12/15
N2 - There are several notions of gonality for graphs. The divisorial gonality dgon(G) of a graph G is the smallest degree of a divisor of positive rank in the sense of Baker–Norine. The stable gonality sgon(G) of a graph G is the minimum degree of a finite harmonic morphism from a refinement of G to a tree, as defined by Cornelissen, Kato and Kool. We show that computing dgon(G) and sgon(G) are NP-hard by a reduction from the maximum independent set problem and the vertex cover problem, respectively. Both constructions show that computing gonality is moreover APX-hard.
AB - There are several notions of gonality for graphs. The divisorial gonality dgon(G) of a graph G is the smallest degree of a divisor of positive rank in the sense of Baker–Norine. The stable gonality sgon(G) of a graph G is the minimum degree of a finite harmonic morphism from a refinement of G to a tree, as defined by Cornelissen, Kato and Kool. We show that computing dgon(G) and sgon(G) are NP-hard by a reduction from the maximum independent set problem and the vertex cover problem, respectively. Both constructions show that computing gonality is moreover APX-hard.
KW - Chip-firing
KW - Computational complexity
KW - Gonality
KW - Graph theory
KW - Tropical geometry
UR - http://www.scopus.com/inward/record.url?scp=85089796472&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2020.08.013
DO - 10.1016/j.dam.2020.08.013
M3 - Article
AN - SCOPUS:85089796472
SN - 0166-218X
VL - 287
SP - 134
EP - 149
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -