We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that none of them can give a performance guarantee. We further analyze the relative strength among the three upper bounds by determining, for every choice of a ratio between any two of them, the largest values it can attain and providing families of instances for which such values can be reached. Our results show that, for each pair of upper bounds, there exist appropriately chosen instances on which either bound is tighter than the other. Our theoretical analysis is complemented by extensive computational experiments on two benchmark datasets: the standard DIMACS instances and randomly generated instances, providing practical insights into the empirical strength of the upper bounds.
Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem / Ciccarelli, F., Dose, V., Furini, F., Monaci, M.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 397:30 January 2027(2027), pp. 73-101. [10.1016/j.dam.2026.09.019]
Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem
Fabio Ciccarelli;Valerio Dose
;Fabio Furini;Marta Monaci
2027
Abstract
We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that none of them can give a performance guarantee. We further analyze the relative strength among the three upper bounds by determining, for every choice of a ratio between any two of them, the largest values it can attain and providing families of instances for which such values can be reached. Our results show that, for each pair of upper bounds, there exist appropriately chosen instances on which either bound is tighter than the other. Our theoretical analysis is complemented by extensive computational experiments on two benchmark datasets: the standard DIMACS instances and randomly generated instances, providing practical insights into the empirical strength of the upper bounds.| File | Dimensione | Formato | |
|---|---|---|---|
|
Ciccarelli_postprint_Strength_2026.pdf
accesso aperto
Note: 10.1016/j.dam.2026.09.019
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
773.08 kB
Formato
Adobe PDF
|
773.08 kB | Adobe PDF | |
|
Ciccarelli_Strength_2026.pdf
accesso aperto
Note: 10.1016/j.dam.2026.09.019
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
2.37 MB
Formato
Adobe PDF
|
2.37 MB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.


