Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running time. For the vertex cover problem, there is a gap between theory and practice when it comes to understanding this tradeoff. On the one hand, it is known that it is NP-hard to approximate a minimum vertex cover within a factor of $\sqrt{2}$. On the other hand, a simple greedy algorithm yields close to optimal approximations in practice. A promising approach towards understanding this discrepancy is to recognize the differences between theoretical worst-case instances and real-world networks. Following this direction, we close the gap between theory and practice by providing an algorithm that efficiently computes nearly optimal vertex cover approximations on hyperbolic random graphs; a network model that closely resembles real-world networks in terms of degree distribution, clustering, and the small-world property. More precisely, our algorithm computes a $(1 + o(1))$-approximation, asymptotically almost surely, and has a running time of $\mathcal{O}(m \log(n))$. The proposed algorithm is an adaptation of the successful greedy approach, enhanced with a procedure that improves on parts of the graph where greedy is not optimal. This makes it possible to introduce a parameter that can be used to tune the tradeoff between approximation performance and running time. Our empirical evaluation on real-world networks shows that this allows for improving over the near-optimal results of the greedy approach.
翻译:在网络中找到最小的顶点覆盖是一个基本的 NP 完整的图形问题。 处理其计算硬度的方法之一, 是将算法( 允许非最佳产出) 的质量性能转换为更好的运行时间。 对于顶点覆盖问题, 当理解这个权衡时, 理论和实践之间存在差距。 一方面, 已知在一个 $\ sqrt{2} 的系数范围内接近一个最小的顶点覆盖很难 NP 。 另一方面, 简单的贪婪算法在实际中接近于最佳的近似值。 理解这一差异的一个有希望的方法是认识到理论最坏情况实例与真实世界网络之间的差别。 遵循这个方向, 我们缩小理论与实践之间的差距, 提供一种有效计算近于最佳的顶点覆盖随机图的近似匹配值; 网络模型与真实世界网络的分布、 集中和小世界的属性非常接近。 更准确地说, 我们的算法在接近于 $ ( o) o (l) o) o- prialalal 的精确度 方法中, 使得正在运行的轨迹运行的轨迹进程。 。 。 在Opral_ 运行中, 运行中, 运行中, 运行中, 运行中 正在 运行中 运行中 运行中 运行中 运行中 运行中 轨道 运行中 运行中 运行中 运行中 。