{"id":"arxiv/2601.05644","url":"https://arxiv.org/abs/2601.05644","tags":["math.OC"],"score":0,"title":"The Maximum Clique Problem under Adversarial Uncertainty: a min-max approach","domain":"math.OC","source":"arxiv","authors":["Immanuel Bomze","Chiara Faccio","Francesco Rinaldi","Giovanni Spisso"],"reviews":0,"subject":"math.OC","summary":"We analyze the problem of identifying large cliques in graphs that are affected by adversarial uncertainty. More specifically, we consider a new formulation, namely the adversarial maximum clique problem, which extends the classical maximum-clique problem to graphs with edges strategically perturbed by an adversary. The proposed mathematical model is thus formulated as a two-player zero-sum game between a clique seeker and an opposing agent. Inspired by regularized continuous reformulations of the maximum-clique problem, we derive a penalized continuous formulation leading to a nonconvex and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-09","reactions":{}}