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 -