Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs

Given a simple graph and a constant γ ∈ ( 0 , 1 ] , a γ -quasi-clique is defined as a subset of vertices that induces a subgraph with an edge density of at least γ . This well-known clique relaxation model arises in a variety of application domains. The maximum γ -quasi-clique problem is to find a γ...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2016-05, Vol.64 (1), p.177-214
Main Authors: Veremyev, Alexander, Prokopyev, Oleg A., Butenko, Sergiy, Pasiliao, Eduardo L.
Format: Article
Language:English
Subjects:
Computer programming
Constants
Convex and Discrete Geometry
Graph theory
Graphs
Integer programming
Linear programming
Management Science
Mathematical analysis
Mathematical models
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Optimization
Statistics
Studies
Systems engineering
Texts
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a simple graph and a constant γ ∈ ( 0 , 1 ] , a γ -quasi-clique is defined as a subset of vertices that induces a subgraph with an edge density of at least γ . This well-known clique relaxation model arises in a variety of application domains. The maximum γ -quasi-clique problem is to find a γ -quasi-clique of maximum cardinality in the graph and is known to be NP -hard. This paper proposes new mixed integer programming (MIP) formulations for solving the maximum γ -quasi-clique problem. The corresponding linear programming (LP) relaxations are analyzed and shown to be tighter than the LP relaxations of the MIP models available in the literature on sparse graphs. The developed methodology is naturally generalized for solving the maximum f ( · ) -dense subgraph problem, which, for a given function f ( · ) , seeks for the largest k such that there is a subgraph induced by k vertices with at least f ( k ) edges. The performance of the proposed exact approaches is illustrated on real-life network instances with up to 10,000 vertices.
ISSN:0926-6003
1573-2894
DOI:10.1007/s10589-015-9804-y