论文标题
一项关于图表问题的调查，在上述和低于保证的值的参数
A Survey on Graph Problems Parameterized Above and Below Guaranteed Values
论文作者
论文摘要
我们调查算法和复杂性的领域，以了解上面或低于保证的值的图形问题，这是Venkatesh Raman开创的研究区域。对于给定的图$ g $而言，这些问题是一种解决方案，其价值至少为$ g（g）+k $或最多$ g（g）-k $，其中$ g（g）$是保证$ g $的任何解决方案所需的值。目的是设计算法，这些算法会在及时找到这种解决方案，其在$ k $中的复杂性与保证中的复杂性是分离的，或者通过棘手的结果来排除这种算法的存在。我们讨论了大量算法和棘手性结果，并通过几个开放问题进行补充。
We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values, a research area which was pioneered by Venkatesh Raman. Those problems seek, for a given graph $G$, a solution whose value is at least $g(G)+k$ or at most $g(G)-k$, where $g(G)$ is a guarantee on the value that any solution on $G$ takes. The goal is to design algorithms which find such solution in time whose complexity in $k$ is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems.
