Stable gonality is computable

zbMATH Open1417.05234arXiv1801.07553MaRDI QIDQ5226830FDOQ5226830

Ragnar Groot Koerkamp, Marieke van der Wegen

Publication date: 1 August 2019

Abstract: Stable gonality is a multigraph parameter that measures the complexity of a graph. It is defined using maps to trees. Those maps, in some sense, divide the edges equally over the edges of the tree; stable gonality asks for the map with the minimum number of edges mapped to each edge of the tree. This parameter is related to treewidth, but unlike treewidth, it distinguishes multigraphs from their underlying simple graphs. Stable gonality is relevant for problems in number theory. In this paper, we show that deciding whether the stable gonality of a given graph is at most a given integer $k$ belongs to the class NP, and we give an algorithm that computes the stable gonality of a graph in $O((1.33n{)}^n{m}^{m}extpoly(n,m))$ time.

Full work available at URL: https://arxiv.org/abs/1801.07553

zbMATH Keywords

algorithmgraph parametergonality

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99)

Cited In (3)

• Computing graph gonality is hard
• Problems hard for treewidth but easy for stable gonality
• Recognizing hyperelliptic graphs in polynomial time

This page was built for publication: Stable gonality is computable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226830)