Practical maximum clique search on 300–900 vertex graphs in a few seconds
A MathOverflow question asks about practical algorithms for finding maximum cliques in graphs of 300–900 vertices within seconds, noting that while research focuses on 1000+ vertex graphs with heuristics, the challenge here is exact solutions for smaller graphs with limited computation time.
Background
A MathOverflow question asks whether the maximum clique problem (finding the largest fully connected subset) can be solved quickly on graphs with 300–900 vertices. While this is a moderately large size for exact clique algorithms, the poster notes these are "real-world" graphs that are relatively sparse (few edges per vertex). The question bridges theoretical computer science (the clique problem is NP-hard, meaning no efficient algorithm is known for all cases) and practical engineering: many real graphs have structure that allows specialized algorithms to finish in seconds. The poster is likely looking for references to branch-and-bound solvers like Cliquer, or newer GPU-based approaches. This matters because fast clique detection has applications in bioinformatics, social network analysis, and cryptography.