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

Fingerprint

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

Cite this