Computing graph gonality is hard

DC Gijswijt, Harry J. Smit, Marieke van der Wegen

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)
53 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)134-149
Number of pages16
JournalDiscrete Applied Mathematics
Volume287
DOIs
Publication statusPublished - 2020

Keywords

  • Gonality
  • Computational complexity
  • Chip-firing
  • Graph theory
  • Tropical geometry

Fingerprint

Dive into the research topics of 'Computing graph gonality is hard'. Together they form a unique fingerprint.

Cite this