dorsal/arxiv
View SchemaThe Maximum Clique Problem under Adversarial Uncertainty: a min-max approach
| Authors | Immanuel Bomze, Chiara Faccio, Francesco Rinaldi, Giovanni Spisso |
|---|---|
| Categories | |
| ArXiv ID | 2601.05644vv1 |
| URL | https://arxiv.org/abs/2601.05644 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
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 nonsmooth optimization problem. We further introduce the notion of stable global solutions, namely points remaining optimal under small perturbations of the penalty parameters, and prove an equivalence between stable global solutions of the continuous reformulation and largest cliques that are common to all the adversarially perturbed graphs. In order to solve the given nonsmooth problem, we develop a first-order and projection-free algorithm based on generalized subdifferential calculus in the sense of Clarke and Goldstein, and establish global sublinear convergence rates for it. Finally, we report numerical experiments on benchmark instances showing that the proposed method efficiently detects large common cliques.
{
"annotation_id": "16dba780-3b30-4f02-b673-24cd24d4749d",
"date_created": "2026-02-17T05:53:03.987000Z",
"date_modified": "2026-02-17T05:53:03.987000Z",
"file_hash": "45f848a68d42733cf0fea420825e4a92190301f568adb371ae042dc709a22756",
"private": false,
"record": {
"abstract": "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 nonsmooth optimization problem. We further introduce the notion of stable global solutions, namely points remaining optimal under small perturbations of the penalty parameters, and prove an equivalence between stable global solutions of the continuous reformulation and largest cliques that are common to all the adversarially perturbed graphs. In order to solve the given nonsmooth problem, we develop a first-order and projection-free algorithm based on generalized subdifferential calculus in the sense of Clarke and Goldstein, and establish global sublinear convergence rates for it. Finally, we report numerical experiments on benchmark instances showing that the proposed method efficiently detects large common cliques.",
"arxiv_id": "2601.05644",
"authors": [
"Immanuel Bomze",
"Chiara Faccio",
"Francesco Rinaldi",
"Giovanni Spisso"
],
"categories": [
"math.OC"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "The Maximum Clique Problem under Adversarial Uncertainty: a min-max approach",
"url": "https://arxiv.org/abs/2601.05644",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "91187ed4-b140-45c3-a7a7-5250a452dd7c",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}