The Maximum Clique Problem under Adversarial Uncertainty: a min-max approach

Immanuel Bomze, Chiara Faccio, Francesco Rinaldi, Giovanni Spisso · 2026

Read The Maximum Clique Problem under Adversarial Uncertainty: a min-max approach by Immanuel Bomze, Chiara Faccio, Francesco Rinaldi, Giovanni Spisso (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05644.txt.

Description

Immanuel Bomze and 3 co-authors formulate, in a 2026 paper, the maximum clique problem under adversarial uncertainty. A clique is a set of graph vertices all connected to each other, and finding the largest one is a classic hard problem. Here an adversary strategically perturbs the graph's edges, so a useful clique should survive those changes.

The model becomes a zero-sum game for two players, one seeking a clique and one working against it. A penalized continuous reformulation leads to a nonconvex, nonsmooth optimization problem. The authors define stable global solutions and prove they match the largest cliques common to all perturbed graphs. Their projection-free algorithm carries global convergence rates, and benchmark tests detected large common cliques efficiently.

Catalog record

CREATORImmanuel Bomze, Chiara Faccio, Francesco Rinaldi, Giovanni Spisso
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-05644

Browse the full library · About the Tower of Babel