论文标题
在近似图形除数等级时
On approximating the rank of graph divisors
论文作者
论文摘要
贝克（Baker）和诺琳（Norine）启动了图形除数作为Riemann-Roch理论的图形理论类似物的研究。图形除数理论的关键概念之一是图形上除法的{\ it carv}。贝克的{\ it专业化引理}很好地说明了等级的重要性，并指出线性系统的维度只能在从曲线到图表的情况下升高，从而导致图和曲线上的分隔线之间的富有成果的交互。 由于其决定性的作用，确定等级是图形除数理论中的一个核心问题。 KISS和TóthMéresz使用芯片射击游戏重新制定了问题，并表明，通过减少最小反馈弧设置问题，计算图表上的除数等级是NP-HARD。 在本文中，我们通过建立芯片发射游戏与最小目标设定选择问题之间的联系来增强他们的结果。作为推论，我们表明，对于任何$ \ varepsilon> 0 $，除非$ p = np $，否则很难在$ o（2^{\ log^{1- \ varepsilon} n} n} n} n} n} n} n} np $ o（2^{\ log^{1- \ varepsilon} n} np $ o（2^{\ log^{1- \ varepsilon} n}）内，排名很难大致近似。此外，假设有浓密的子图猜想，对于任何$ \ varepsilon> 0 $，排名很难在$ o（n^{1/4- \ varepsilon}）$ y;
Baker and Norine initiated the study of graph divisors as a graph-theoretic analogue of the Riemann-Roch theory for Riemann surfaces. One of the key concepts of graph divisor theory is the {\it rank} of a divisor on a graph. The importance of the rank is well illustrated by Baker's {\it Specialization lemma}, stating that the dimension of a linear system can only go up under specialization from curves to graphs, leading to a fruitful interaction between divisors on graphs and curves. Due to its decisive role, determining the rank is a central problem in graph divisor theory. Kiss and Tóthméresz reformulated the problem using chip-firing games, and showed that computing the rank of a divisor on a graph is NP-hard via reduction from the Minimum Feedback Arc Set problem. In this paper, we strengthen their result by establishing a connection between chip-firing games and the Minimum Target Set Selection problem. As a corollary, we show that the rank is difficult to approximate to within a factor of $O(2^{\log^{1-\varepsilon}n})$ for any $\varepsilon > 0$ unless $P=NP$. Furthermore, assuming the Planted Dense Subgraph Conjecture, the rank is difficult to approximate to within a factor of $O(n^{1/4-\varepsilon})$ for any $\varepsilon>0$.
