Computing graph gonality is hard

Title

Computing graph gonality is hard

 Author

Gijswijt, Dion (TU Delft Discrete Mathematics and Optimization) ORCID 0000-0003-0734-4511
Smit, Harry J. (Universiteit Utrecht)
van der Wegen, Marieke (Universiteit Utrecht)

Date

2020

 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.

 Subject

Gonality
Computational complexity
Chip-firing
Graph theory
Tropical geometry

 To reference this document use:

http://resolver.tudelft.nl/uuid:415dcfad-a7f2-4845-ac09-1b9a7d0cdc5c

 DOI

https://doi.org/10.1016/j.dam.2020.08.013

 ISSN

0166-218X

 Source

Discrete Applied Mathematics, 287, 134-149

 Part of collection

Institutional Repository

 Document type

journal article

 Rights

© 2020 Dion Gijswijt, Harry J. Smit, Marieke van der Wegen
Files
PDF 1_s2.0_S0166218X20303796_main.pdf 587.45 KB
Close viewer