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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	SOFSEM 2019
Subtitle of host publication	Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
Editors	Barbara Catania, Giovanni Pighizzini, Rastislav Královič, Jerzy Nawrocki
Place of Publication	Cham
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 - 11 Jan 2019
Event	45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Nový Smokovec, Slovakia Duration: 27 Jan 2019 → 30 Jan 2019

Publication series

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

Conference

Conference	45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
Country/Territory	Slovakia
City	Nový Smokovec
Period	27/01/19 → 30/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.

Access to Document

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

Cite this

Bodlaender, H. L., van der Wegen, M., & van der Zanden, T. C. (2019). Stable divisorial gonality is in NP. In B. Catania, G. Pighizzini, R. Královič, & J. Nawrocki (Eds.), SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings (pp. 81-93). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11376 LNCS). Springer. https://doi.org/10.1007/978-3-030-10801-4_8

Bodlaender, Hans L. ; van der Wegen, Marieke ; van der Zanden, Tom C. / 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, Proceedings. editor / Barbara Catania ; Giovanni Pighizzini ; Rastislav Královič ; Jerzy Nawrocki. Cham : Springer, 2019. pp. 81-93 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b32307741e7d46c29de4e3f5bf5102ee,

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

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

year = "2019",

month = jan,

day = "11",

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

language = "English",

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

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "81--93",

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

booktitle = "SOFSEM 2019",

address = "Germany",

note = "45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 ; Conference date: 27-01-2019 Through 30-01-2019",

}

Bodlaender, HL, van der Wegen, M & van der Zanden, TC 2019, Stable divisorial gonality is in NP. in B Catania, G Pighizzini, R Královič & J Nawrocki (eds), SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11376 LNCS, Springer, Cham, pp. 81-93, 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018, Nový Smokovec, Slovakia, 27/01/19. https://doi.org/10.1007/978-3-030-10801-4_8

Stable divisorial gonality is in NP. / Bodlaender, Hans L.; van der Wegen, Marieke; van der Zanden, Tom C.
SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. ed. / Barbara Catania; Giovanni Pighizzini; Rastislav Královič; Jerzy Nawrocki. Cham: Springer, 2019. p. 81-93 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11376 LNCS).

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 - van der Wegen, Marieke

AU - van der Zanden, Tom C.

PY - 2019/1/11

Y1 - 2019/1/11

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

UR - http://www.scopus.com/inward/record.url?scp=85062362936&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:85062362936

SN - 978-3-030-10800-7

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 81

EP - 93

BT - SOFSEM 2019

A2 - Catania, Barbara

A2 - Pighizzini, Giovanni

A2 - Královič, Rastislav

A2 - Nawrocki, Jerzy

PB - Springer

CY - Cham

T2 - 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018

Y2 - 27 January 2019 through 30 January 2019

ER -

Bodlaender HL, van der Wegen M, van der Zanden TC. Stable divisorial gonality is in NP. In Catania B, Pighizzini G, Královič R, Nawrocki J, editors, SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Cham: Springer. 2019. p. 81-93. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-10801-4_8

Stable divisorial gonality is in NP

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this