论文标题
计算较高的图很难
Computing higher graph gonality is hard
论文作者
论文摘要
在多编码的分隔线理论中，图形的$ r^{th} $分隔度是该图上等级$ r $ divisor的最低程度。 Gijswijt等人证明了这一点。有限图的第一个分区性是计算的NP-HARD。我们概括了他们的论点，以证明计算所有$ r $的有限图的$ r^{th} $ divisorial gonality是NP-HARD。我们使用此结果来证明，计算有限图的$ r^{th} $稳定的分区gonality是NP-HARD，并计算$ r^{th} $ divisorial gonality for Metric图。我们还证明了这些问题是APX，我们研究了这些问题的NP完整性。
In the theory of divisors on multigraphs, the $r^{th}$ divisorial gonality of a graph is the minimum degree of a rank $r$ divisor on that graph. It was proved by Gijswijt et al. that the first divisorial gonality of a finite graph is NP-hard to compute. We generalize their argument to prove that it is NP-hard to compute the $r^{th}$ divisorial gonality of a finite graph for all $r$. We use this result to prove that it is NP-hard to compute $r^{th}$ stable divisorial gonality for a finite graph, and to compute $r^{th}$ divisorial gonality for a metric graph. We also prove these problems are APX-hard, and we study the NP-completeness of these problems.
