A γ-quasi-clique is a simple and undirected graph with edge density of at least γ. Given a graph G, the maximum γ-quasi-clique problem (γ-QCP) consists of finding an induced γ-quasi-clique with the maximum number of vertices. γ-QCP generalizes the well-known maximum clique problem and its solution is useful for detecting dense subgraphs. After reviewing known integer linear programming formulations and dual bounds for γ-QCP, a new formulation obtained by decomposing star inequalities and combining edge inequalities is proposed. The model has an exponential number of variables but a linear number of constraints and its linear relaxation allows the computation by column generation of dual bounds for large and dense graphs. The connectivity of γ-quasi-cliques is also discussed and a new sufficient connectivity condition presented. An extensive computational experience shows the quality of the computed dual bounds and their performance in a branch-and-price framework, as well as the practical effectiveness of the connectivity condition.

LP-based dual bounds for the maximum quasi-clique problem / Marinelli, F.; Pizzuti, A.; Rossi, F.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 296:(2021), pp. 118-140. [10.1016/j.dam.2020.02.003]

LP-based dual bounds for the maximum quasi-clique problem

Marinelli F.
;
Pizzuti A.;
2021-01-01

Abstract

A γ-quasi-clique is a simple and undirected graph with edge density of at least γ. Given a graph G, the maximum γ-quasi-clique problem (γ-QCP) consists of finding an induced γ-quasi-clique with the maximum number of vertices. γ-QCP generalizes the well-known maximum clique problem and its solution is useful for detecting dense subgraphs. After reviewing known integer linear programming formulations and dual bounds for γ-QCP, a new formulation obtained by decomposing star inequalities and combining edge inequalities is proposed. The model has an exponential number of variables but a linear number of constraints and its linear relaxation allows the computation by column generation of dual bounds for large and dense graphs. The connectivity of γ-quasi-cliques is also discussed and a new sufficient connectivity condition presented. An extensive computational experience shows the quality of the computed dual bounds and their performance in a branch-and-price framework, as well as the practical effectiveness of the connectivity condition.
2021
File in questo prodotto:
File Dimensione Formato  
An_analysis_of_dual_bounds_for_the_maximum_quasi_clique_problem.pdf

Open Access dal 05/03/2022

Tipologia: Documento in post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza d'uso: Creative commons
Dimensione 2.13 MB
Formato Adobe PDF
2.13 MB Adobe PDF Visualizza/Apri
1-s2.0-S0166218X20300627-main.pdf

Solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza d'uso: Tutti i diritti riservati
Dimensione 1.07 MB
Formato Adobe PDF
1.07 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11566/293642
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact