Solving maximum clique in sparse graphs: an $$O(nm+n2^{d/4})$$O(nm+n2d/4) algorithm for $$d$$d-degenerate graphs
Solving maximum clique in sparse graphs: an $$O(nm+n2^{d/4})$$O(nm+n2d/4) algorithm for $$d$$d-degenerate graphs
复制标题
求解稀疏图中的最大团：$$O(nm n2^{d/4})$$O(nm n2d/4) 算法用于 $$d$$d 简并图
作者：
Austin Buchanan;J. Walteros;S. Butenko;P. Pardalos
给出了一个以图的退化程度$$d$$d为参数的图的最大团问题的算法，该算法的运行时间为$$O\Left(nm+n T_d\right)$$onm+ntd，其中$$T_d$$td是在$$d$$d个顶点上求解任意图的最大团问题的时间.到目前为止，Robson的最佳界是$$T_d=O(2^{d/4})$$TD=O(2d/4)。这表明在$$d\log2m+O(1)$$d≤4log2m+O(1)的图中，最大团问题在$$O(Nm)$$O(Nm)时间内是可解的。该算法的运行时间分析简单；给出一个求解小图中最大团的子例程，算法易于实现；易于并行化。对于Bianconi-Marsili幂定律随机图，它以高概率运行在$$2^{O(Sqrt{n})}$$2O(N)时间内。我们扩展了基于公共邻域的图不变量的方法，以较大的多项式因子为代价产生了第二个具有较小指数的算法。
We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy $$d$$d. The algorithm runs in $$O\left( nm+n T_d \right) $$Onm+nTd time, where $$T_d$$Td is the time to solve the maximum clique problem in an arbitrary graph on $$d$$d vertices. The best bound as of now is $$T_d=O(2^{d/4})$$Td=O(2d/4) by Robson. This shows that the maximum clique problem is solvable in $$O(nm)$$O(nm) time in graphs for which $$d \le 4 \log _2 m + O(1)$$d≤4log2m+O(1). The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in $$2^{O(\sqrt{n})}$$2O(n) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.