Hard instances for the maximum clique problem with high probability

Abstract

The Maximum Clique problem is a classic graph-theoretical optimization problem with the objective of finding a maximum clique in a given input graph. Despite numerous theoretical hardness results, empirical studies suggest that the problem is often easier than expected. In this work, we explore a class of Branch & Bound algorithms for solving Maximum Clique and how they make the problem more tractable in practice. We approach the relationship between cliques and proper vertex colorings and derive the asymptotic growth of the number of colorings in random graphs with high probability. Using this result paired with a coloring-to-clique polynomial reduction in the literature, we generate new Maximum Clique instances and analyze them. Moreover, we examine a family of instances from the literature that induce exponential runtime on a widely adopted subclass of Branch & Bound algorithms that use a chromatic upper bound to prune branches. We propose a preprocessing method that enables these algorithms to solve such instances in linear time on their size. Furthermore, we introduce a randomized construction that produces graphs resistant to this preprocessing and still exhibit exponential runtime for these algorithms, even if the upper bound uses the fractional chromatic number instead, which is a tighter bound. Finally, we run some computational tests to validate our analyses.