Computing graph gonality is hard
Computing graph gonality is hard
复制标题
计算图的连通性很困难
DOI：
10.1016/j.dam.2020.08.013
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. V. D. Wegen
中科院分区：
文献类型：
--
作者：
D. Gijswijt;H. Smit;M. V. D. Wegen
图的多边性有多种概念。图 G 的除数 gonality dgon (G) 是 Baker-Norine 意义上的正秩除数的最小度。图 G 的稳定多边性 sgon (G) 是从 G 细化到树的有限调和态射的最小度，如 Cornelissen、Kato 和 Kool 所定义。我们通过分别从最大独立集问题和顶点覆盖问题来证明计算 dgon (G) 和 sgon (G) 是 NP 困难的。两种结构都表明，计算 Goality 也是 APX 困难的。
There are several notions of gonality for graphs. The divisorial gonality dgon (G) of a graph G is the smallest degree of a divisor of positive rank in the sense of Baker–Norine. The stable gonality sgon (G) of a graph G is the minimum degree of a finite harmonic morphism from a refinement of G to a tree, as defined by Cornelissen, Kato and Kool. We show that computing dgon (G) and sgon (G) are NP-hard by a reduction from the maximum independent set problem and the vertex cover problem, respectively. Both constructions show that computing gonality is moreover APX-hard.