Computing graph gonality is hard

Dion Gijswijt; Harry Smit; Marieke van der Wegen

doi:10.1016/j.dam.2020.08.013

Computing graph gonality is hard

Dion Gijswijt^*
, Harry Smit
, Marieke van der Wegen

^*Corresponding author for this work

Delft University of Technology

Research output: Contribution to journal › Article › Academic › peer-review

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 language	English
Pages (from-to)	134-149
Number of pages	16
Journal	Discrete Applied Mathematics
Volume	287
DOIs	https://doi.org/10.1016/j.dam.2020.08.013
Publication status	Published - 15 Dec 2020

Funding

We are very grateful to Gunther Cornelissen for his valuable comments on earlier versions of this paper.

Keywords

Chip-firing
Computational complexity
Gonality
Graph theory
Tropical geometry

Access to Document

10.1016/j.dam.2020.08.013

1-s2.0-S0166218X20303796-mainFinal published version, 580 KBLicence: CC BY

Cite this

@article{01b496d324504b09868f9b4460aa9b38,

title = "Computing graph gonality is hard",

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.",

keywords = "Chip-firing, Computational complexity, Gonality, Graph theory, Tropical geometry",

author = "Dion Gijswijt and Harry Smit and \{van der Wegen\}, Marieke",

year = "2020",

month = dec,

day = "15",

doi = "10.1016/j.dam.2020.08.013",

language = "English",

volume = "287",

pages = "134--149",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier BV",

}

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 - https://www.scopus.com/pages/publications/85089796472

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 -

Computing graph gonality is hard

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this