In 1965, T.S. Motzkin and E. G. 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. Over the years, this seminal finding has inspired a number of studies aimed at characterizing the properties of the (local and global) solutions of the Motzkin–Straus program. The result has also been generalized in various ways and has served as the basis for establishing new bounds on the clique number and developing powerful clique-finding heuristics. Despite the extensive work done on the subject, apart from a few exceptions, the existing literature pays little or no attention to the Karush–Kuhn–Tucker (KKT) points of the program. In the conviction that these points might reveal interesting structural properties of the graph underlying the program, this paper tries to fill in the gap. In particular, we study the generalized KKT points of a parameterized version of the Motzkin–Straus program, which are defined via a relaxation of the usual first-order optimality conditions, and we present a number of results that shed light on the symmetries and regularities of certain substructures associated with the underlying graph. These combinatorial structures are further analyzed using barycentric coordinates, thereby providing a link to a related quadratic program that encodes local structural properties of the graph. This turns out to be particularly useful in the study of the generalized KKT points associated with a certain class of graphs that generalize the notion of a star graph. Finally, we discuss the associations between the generalized KKT points of the Motzkin–Straus program and the so-called replicator dynamics, thereby offering an alternative, dynamical-system perspective on the results presented in the paper.

On generalized KKT points for the Motzkin–Straus program / Beretta, Guglielmo; Torcinovich, Alessandro; Pelillo, Marcello. - In: JOURNAL OF GLOBAL OPTIMIZATION. - ISSN 0925-5001. - ELETTRONICO. - 91:(2025), pp. 535-557. [10.1007/s10898-024-01457-2]

On generalized KKT points for the Motzkin–Straus program

Beretta, Guglielmo;
2025

Abstract

In 1965, T.S. Motzkin and E. G. 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. Over the years, this seminal finding has inspired a number of studies aimed at characterizing the properties of the (local and global) solutions of the Motzkin–Straus program. The result has also been generalized in various ways and has served as the basis for establishing new bounds on the clique number and developing powerful clique-finding heuristics. Despite the extensive work done on the subject, apart from a few exceptions, the existing literature pays little or no attention to the Karush–Kuhn–Tucker (KKT) points of the program. In the conviction that these points might reveal interesting structural properties of the graph underlying the program, this paper tries to fill in the gap. In particular, we study the generalized KKT points of a parameterized version of the Motzkin–Straus program, which are defined via a relaxation of the usual first-order optimality conditions, and we present a number of results that shed light on the symmetries and regularities of certain substructures associated with the underlying graph. These combinatorial structures are further analyzed using barycentric coordinates, thereby providing a link to a related quadratic program that encodes local structural properties of the graph. This turns out to be particularly useful in the study of the generalized KKT points associated with a certain class of graphs that generalize the notion of a star graph. Finally, we discuss the associations between the generalized KKT points of the Motzkin–Straus program and the so-called replicator dynamics, thereby offering an alternative, dynamical-system perspective on the results presented in the paper.
File in questo prodotto:
File Dimensione Formato  
2305.08519v2.pdf

embargo fino al 23/12/2025

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: Pubblico - Tutti i diritti riservati
Dimensione 862.27 kB
Formato Adobe PDF
862.27 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
s10898-024-01457-2.pdf

accesso riservato

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 689.36 kB
Formato Adobe PDF
689.36 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2996348