Why Is Maximum Clique Often Easy in Practice?
Why Is Maximum Clique Often Easy in Practice?
复制标题
DOI：
10.1287/opre.2019.1970
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
J. Walteros;Austin Buchanan
中科院分区：
文献类型：
--
作者：
J. Walteros;Austin Buchanan
直到今天，最大团问题仍然是一个计算上具有挑战性的问题。事实上，尽管研究人员尽了最大的努力，仍然存在未解决的具有一千个顶点的基准实例。然而，相对简单的算法可以在几秒钟内解决具有数百万个顶点的现实生活实例。为什么会这样呢？为什么这个问题在许多自然形成的网络中如此容易？在本文中，我们提供了一个解释。首先，我们观察到图的团数ω在大多数现实情况下非常接近图的退化度d。这一观察激发了本文的主要贡献，这是一个最大团问题的算法，该算法在图的大小上以时间多项式运行，但在团数ω与其基于退化的上界d + 1之间的差距g：=（d+ 1）− ω中呈指数关系。当这个间隙g可以被视为一个常数时，就像现实生活中的图一样，所提出的算法运行时间为O（dm）= O（m）。这为这些情况的明显容易性提供了严格的解释，尽管在最坏的情况下问题是棘手的。此外，我们所提出的算法的实现实际上是实际的竞争与文献中的最佳方法。
To this day, the maximum clique problem remains a computationally challenging problem. Indeed, despite researchers’ best efforts, there exist unsolved benchmark instances with one thousand vertices. However, relatively simple algorithms solve real-life instances with millions of vertices in a few seconds. Why is this the case? Why is the problem apparently so easy in many naturally occurring networks? In this paper, we provide an explanation. First, we observe that the graph’s clique number ω is very near to the graph’s degeneracy d in most real-life instances. This observation motivates a main contribution of this paper, which is an algorithm for the maximum clique problem that runs in time polynomial in the size of the graph, but exponential in the gap g := (d+ 1)− ω between the clique number ω and its degeneracy-based upper bound d + 1. When this gap g can be treated as a constant, as is often the case for real-life graphs, the proposed algorithm runs in time O(dm) = O(m). This provides a rigorous explanation for the apparent easiness of these instances despite the intractability of the problem in the worst case. Further, our implementation of the proposed algorithm is actually practical—competitive with the best approaches from the literature.