Computing graph gonality is hard

Journal article (2020)

Authors

Dion Gijswijt Discrete Mathematics and Optimization - EEMCS
Harry J. Smit Universiteit Utrecht
Marieke van der Wegen Universiteit Utrecht
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2020 Dion Gijswijt, Harry J. Smit, Marieke van der Wegen
DOI: https://doi.org/10.1016/j.dam.2020.08.013
More Info
expand_more

Published Date

2020

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

Abstract

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.