| Итог: | 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)^nm^m \text{poly}(n,m))$ time.
|
|---|