Stable Divisorial Gonality is in NP

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

doi:10.1007/978-3-030-10801-4_8

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 proceeding › Conference contribution › Academic › peer-review

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 2p(n)
for a polynomial p.

Original language	English
Title of host publication	SOFSEM 2019: Theory and Practice of Computer Science
Subtitle of host publication	45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings
Editors	Barbara Catania, Rastislav Královič, Jerzy Nawrocki, Giovanni Pighizzini
Publisher	Springer
Pages	81-93
Number of pages	13
ISBN (Electronic)	978-3-030-10801-4
ISBN (Print)	978-3-030-10800-7
DOIs	https://doi.org/10.1007/978-3-030-10801-4_8
Publication status	Published - 2019

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11376

Access to Document

10.1007/978-3-030-10801-4_8

Bodlaender2019_Chapter_StableDivisorialGonalityIsInNPFinal published version, 292 KBLicence: Taverne

Cite this

Bodlaender, H. L., Wegen, M. V. D., & Zanden, T. C. V. D. (2019). Stable Divisorial Gonality is in NP. In B. Catania, R. Královič, J. Nawrocki, & G. Pighizzini (Eds.), SOFSEM 2019: Theory and Practice of Computer Science: 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings (pp. 81-93). (Lecture Notes in Computer Science; Vol. 11376). Springer. https://doi.org/10.1007/978-3-030-10801-4_8

Bodlaender, Hans L. ; Wegen, Marieke van der ; Zanden, Tom C. van der. / Stable Divisorial Gonality is in NP. SOFSEM 2019: Theory and Practice of Computer Science: 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings. editor / Barbara Catania ; Rastislav Královič ; Jerzy Nawrocki ; Giovanni Pighizzini. Springer, 2019. pp. 81-93 (Lecture Notes in Computer Science).

@inproceedings{c236fc7bd2e143d2945c828bd827910d,

title = "Stable Divisorial Gonality is in NP",

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 2p(n)for a polynomial p.",

author = "Bodlaender, {Hans L.} and Wegen, {Marieke van der} and Zanden, {Tom C. van der}",

year = "2019",

doi = "10.1007/978-3-030-10801-4_8",

language = "English",

isbn = "978-3-030-10800-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "81--93",

editor = "{ Catania}, Barbara and Kr{\'a}lovi{\v c}, {Rastislav } and Nawrocki, {Jerzy } and Pighizzini, {Giovanni }",

booktitle = "SOFSEM 2019: Theory and Practice of Computer Science",

}

Bodlaender, HL , Wegen, MVD & Zanden, TCVD 2019, Stable Divisorial Gonality is in NP. in B Catania, R Královič, J Nawrocki & G Pighizzini (eds), SOFSEM 2019: Theory and Practice of Computer Science: 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11376, Springer, pp. 81-93. https://doi.org/10.1007/978-3-030-10801-4_8

Stable Divisorial Gonality is in NP. / Bodlaender, Hans L.; Wegen, Marieke van der; Zanden, Tom C. van der.
SOFSEM 2019: Theory and Practice of Computer Science: 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings. ed. / Barbara Catania; Rastislav Královič; Jerzy Nawrocki; Giovanni Pighizzini. Springer, 2019. p. 81-93 (Lecture Notes in Computer Science; Vol. 11376).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Stable Divisorial Gonality is in NP

AU - Bodlaender, Hans L.

AU - Wegen, Marieke van der

AU - Zanden, Tom C. van der

PY - 2019

Y1 - 2019

N2 - 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 2p(n)for a polynomial p.

AB - 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 2p(n)for a polynomial p.

U2 - 10.1007/978-3-030-10801-4_8

DO - 10.1007/978-3-030-10801-4_8

M3 - Conference contribution

SN - 978-3-030-10800-7

T3 - Lecture Notes in Computer Science

SP - 81

EP - 93

BT - SOFSEM 2019: Theory and Practice of Computer Science

A2 - Catania, Barbara

A2 - Královič, Rastislav

A2 - Nawrocki, Jerzy

A2 - Pighizzini, Giovanni

PB - Springer

ER -

Bodlaender HL , Wegen MVD, Zanden TCVD. Stable Divisorial Gonality is in NP. In Catania B, Královič R, Nawrocki J, Pighizzini G, editors, SOFSEM 2019: Theory and Practice of Computer Science: 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings. Springer. 2019. p. 81-93. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-10801-4_8

Stable Divisorial Gonality is in NP

Abstract

Publication series

Access to Document

Fingerprint

Cite this