In a seminal 1965 paper, Motzkin and Straus established an elegant connection between the clique number of a graph and the global maxima of a quadratic program defined on the standard simplex. Since then, the result has been the subject of intensive research and has served as the motivation for a number of heuristics and bounds for the maximum clique problem. Most of the studies available in the literature, however, focus typically on the local/global solutions of the program, and little or no attention has been devoted so far to the study of its Karush-Kuhn-Tucker (KKT) points. In contrast, in this paper we study the properties of (a parameterized version of) the Motzkin-Straus program and show that its KKT points can provide interesting structural information and are in fact associated with certain regular sub-structures of the underlying graph.
A Note on the KKT Points for the Motzkin-Straus Program / Beretta, G.; Torcinovich, A.; Pelillo, M.. - ELETTRONICO. - (2023). [10.48550/ARXIV.2305.08519]
A Note on the KKT Points for the Motzkin-Straus Program
Beretta, G.;
2023
Abstract
In a seminal 1965 paper, Motzkin and Straus established an elegant connection between the clique number of a graph and the global maxima of a quadratic program defined on the standard simplex. Since then, the result has been the subject of intensive research and has served as the motivation for a number of heuristics and bounds for the maximum clique problem. Most of the studies available in the literature, however, focus typically on the local/global solutions of the program, and little or no attention has been devoted so far to the study of its Karush-Kuhn-Tucker (KKT) points. In contrast, in this paper we study the properties of (a parameterized version of) the Motzkin-Straus program and show that its KKT points can provide interesting structural information and are in fact associated with certain regular sub-structures of the underlying graph.File | Dimensione | Formato | |
---|---|---|---|
2305.08519.pdf
accesso aperto
Descrizione: Manuscript
Tipologia:
1. Preprint / submitted version [pre- review]
Licenza:
PUBBLICO - Tutti i diritti riservati
Dimensione
481.15 kB
Formato
Adobe PDF
|
481.15 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2982472