Solving maximum clique in sparse graphs: an $$O(nm+n2^{d/4})$$ algorithm for $$d$$ -degenerate graphs
Tóm tắt
We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy
$$d$$
. The algorithm runs in
$$O\left( nm+n T_d \right) $$
time, where
$$T_d$$
is the time to solve the maximum clique problem in an arbitrary graph on
$$d$$
vertices. The best bound as of now is
$$T_d=O(2^{d/4})$$
by Robson. This shows that the maximum clique problem is solvable in
$$O(nm)$$
time in graphs for which
$$d \le 4 \log _2 m + 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})}$$
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.
Tài liệu tham khảo
Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D.: Graph Partitioning and Graph Clustering, vol. 588. American Mathematical Society, Providence (2013)
Bianconi, G., Marsili, M.: Emergence of large cliques in random scale-free networks. Europhys. Lett. 74(4), 740 (2006)
Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Handbook of Combinatorial Optimization, pp. 1–74. Springer, Berlin (1999)
Bourgeois, N., Escoffier, B., Paschos, V.T., van Rooij, J.M.M.: Fast algorithms for max independent set. Algorithmica. 62(1–2), 382–415 (2012)
Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)
Chung, F.: Graph theory in the information age. Notices AMS 57(6), 726–732 (2010)
Eppstein, D., Löffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: Algorithms and Computation, pp. 403–414 (2010)
Lick, D.R., White, A.T.: k-Degenerate graphs. Canad. J. Math 22, 1082–1096 (1970)
Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417–427 (1983)
Robson, J.M.: Finding a maximum independent set in time \({O}(2^{n/4})\). LaBRI, Université de Bordeaux I, Technical report (2001)
Verma, A., Buchanan, A., Butenko, S.: Solving the maximum clique and vertex coloring problems on very large sparse networks. Working paper, Department of Industrial and Systems Engineering, Texas A &M University, College Station, TX (2012)