Ragnar Groot Koerkamp ; Marieke van der Wegen - Stable gonality is computable

dmtcs:4931 - Discrete Mathematics & Theoretical Computer Science, June 13, 2019, vol. 21 no. 1, ICGT 2018 - https://doi.org/10.23638/DMTCS-21-1-10
Stable gonality is computableArticle

Authors: Ragnar Groot Koerkamp ; Marieke van der Wegen

    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.


    Volume: vol. 21 no. 1, ICGT 2018
    Published on: June 13, 2019
    Accepted on: April 22, 2019
    Submitted on: October 30, 2018
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Data Structures and Algorithms,Mathematics - Combinatorics,Mathematics - Number Theory

    Consultation statistics

    This page has been seen 653 times.
    This article's PDF has been downloaded 184 times.