Paper Info
Title
Lp-Based Dual Bounds For The Maximum Quasi-Clique Problem
Abstract
A gamma-quasi-clique is a simple and undirected graph with edge density of at least gamma. Given a graph G, the maximum gamma-quasi-clique problem (gamma-QCP) consists of finding an induced gamma-quasi-clique with the maximum number of vertices. gamma-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 gamma-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 gamma-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. (C) 2020 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.dam.2020.02.003
DISCRETE APPLIED MATHEMATICS
Keywords
DocType
Volume
Quasi-clique, Mixed integer programming, Integer reformulation
Journal
296
ISSN
Citations 
PageRank 
0166-218X
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Fabrizio Marinelli125820.55
Andrea Pizzuti221.39
Fabrizio Rossi314016.33