Stable divisorial gonality is in NP

Hans L. Bodlaender, Marieke van der Wegen, Tom C. van der Zanden

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

Divisorial gonality and stable divisorial gonality are graph parameters, which have an origin in algebraic geometry. Divisorial gonality of a connected graph G can be defined with help of a chip firing game on G. The stable divisorial gonality of G is the minimum divisorial gonality over all subdivisions of edges of G. In this paper we prove that deciding whether a given connected graph has stable divisorial gonality at most a given integer k belongs to the class NP. Combined with the result that (stable) divisorial gonality is NP-hard by Gijswijt, we obtain that stable divisorial gonality is NP-complete. The proof consists of a partial certificate that can be verified by solving an Integer Linear Programming instance. As a corollary, we have that the number of subdivisions needed for minimum stable divisorial gonality of a graph with n vertices is bounded by 2 p(n) for a polynomial p.

Original languageEnglish
Title of host publicationSOFSEM 2019
Subtitle of host publicationTheory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
EditorsBarbara Catania, Giovanni Pighizzini, Rastislav Královič, Jerzy Nawrocki
Place of PublicationCham
PublisherSpringer
Pages81-93
Number of pages13
ISBN (Electronic)978-3-030-10801-4
ISBN (Print)978-3-030-10800-7
DOIs
Publication statusPublished - 11 Jan 2019
Event45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Nový Smokovec, Slovakia
Duration: 27 Jan 201930 Jan 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11376 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
Country/TerritorySlovakia
CityNový Smokovec
Period27/01/1930/01/19

Funding

H. L. Bodlaender—This work was supported by the NETWORKS project, funded by the Netherlands Organization for Scientific Research NWO under project no. 024.002.003.

Fingerprint

Dive into the research topics of 'Stable divisorial gonality is in NP'. Together they form a unique fingerprint.

Cite this