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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.