Instances for the Maximum Clique Problem with Hardness Guarantees
Resumo
Branch and bound algorithms which use (an estimate on) the chromatic number as the bounding function are reported among the best known exact algorithms for the maximum clique problem. Their average running time is known to be quasi-polynomial and describing families of instances which induce exponential running time for these algorithms is a non-trivial issue. We describe two such families of graphs. We prove that graphs in the first family induce asymptotically higher running time than the average for algorithms whose running time is Ω(c(G)) where c(G) is the number of cliques in G. We also prove that graphs in the second family induce exponential running time for branch and bound algorithms which use the chromatic number as the bounding function.
Referências
Campêlo, M., Campos, V., and Corrêa, R. (2008). On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics, 156(7):1097–1111.
Cornaz, D. and Jost, V. (2008). A one-to-one correspondence between colorings and stable sets. Operations Research Letters, 36(6):673–676.
Downey, R. and Fellows, M. (1995). Parameterized computational feasibility. In Clote, P. and Remmel, J. B., editors, Feasible Mathematics II, pages 219–244, Boston, MA. Birkhäuser Boston.
Johnson, D. and Trick, M., editors (1996). Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, volume 26. American Mathematical Society, Boston, MA, USA.
Karp, R. (1972). Reducibility among combinatorial problems. In Complexity of computer computations, pages 85–103. Springer.
Lavnikevich, N. (2013). On the complexity of maximum clique algorithms: usage of coloring heuristics leads to the (2/5) algorithm running time lower bound.
Pittel, B. (1982). On the probable behaviour of some algorithms for finding the stability number of a graph. Mathematical Proceedings of the Cambridge Philosophical Society, 92:511–526.
San Segundo, P., Lopez, A., and Pardalos, P. M. (2016). A new exact maximum clique algorithm for large and massive sparse graphs. Computers & Operations Research, 66:81–94.
Zuckerman, D. (2006). Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’06, pages 681–690, New York, NY, USA. Association for Computing Machinery.
Züge, A. and Carmo, R. (2018). On comparing algorithms for the maximum clique problem. Discrete Applied Mathematics, 247.
