论文标题
在常规图中的细粒度精确计算上
On Fine-Grained Exact Computation in Regular Graphs
论文作者
论文摘要
我们表明，除非ETH失败，否则没有用于计算D期限图中最大独立集问题的精确解决方案的小指数时间算法。我们扩展了我们的方法，以表明它有助于为其他覆盖问题（例如顶点覆盖物和集团）提供下限。我们利用构造来显示5个规则平面图上MIS的NP硬度，从而在常规平面图上关闭了问题的确切复杂性状态。
We show that there is no subexponential time algorithm for computing the exact solution of the maximum independent set problem in d-regular graphs unless ETH fails. We expand our method to show that it helps to provide lower bounds for other covering problems such as vertex cover and clique. We utilize the construction to show the NP-hardness of MIS on 5-regular planar graphs, closing the exact complexity status of the problem on regular planar graphs.
