{"ID":2865284,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.22245","arxiv_id":"2509.22245","title":"Less is More: Faster Maximum Clique Search by Work-Avoidance","abstract":"The maximum clique (MC) problem is a challenging graph mining problem which, due to its NP-hard nature, can take a substantial amount of execution time. The MC problem is dominated by set intersection operations similar to Maximal Clique Enumeration, however it differs in requiring to find only a clique of maximum size. As such, key to the problem is to demonstrate efficiently that a particular part of the search space does not contain a maximum clique, allowing to skip over major parts of the search space. We present a number of techniques to optimize MC search in light of leaving major parts of the search space unvisited, including (i) an efficient, lazily constructed graph representation; (ii) filtering prior to initiating a detailed search; (iii) efficient early-exit intersection algorithms; (iv) exploiting algorithmic choice. These techniques result in a speedup of up to 38.9x compared to PMC, which is the most comparable algorithm, and a speedup up to 11x over MC-BRB.","short_abstract":"The maximum clique (MC) problem is a challenging graph mining problem which, due to its NP-hard nature, can take a substantial amount of execution time. The MC problem is dominated by set intersection operations similar to Maximal Clique Enumeration, however it differs in requiring to find only a clique of maximum size...","url_abs":"https://arxiv.org/abs/2509.22245","url_pdf":"https://arxiv.org/pdf/2509.22245v1","authors":"[\"Hans Vandierendonck\"]","published":"2025-09-26T11:59:42Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.PF\"]","methods":"[]","has_code":false}