GAINESVILLE:  Vladimir Boginski, Assistant Professor of Industrial and Systems Engineering, will deliver the graduate seminar entitled “The Maximum Quasi-Clique Problem:  Exact and Asymptotic Approaches” on Thursday, October 13, 2011 at 4:05 p.m. in McCarthy Hall A, Room 2186.

The problem of identifying the largest quasi-clique in a network is considered. A quasi-clique is a cluster of vertices that has a pre-defined required edge density. Quasi-cliques are density-based relaxations of the well-known concept of a clique, which provide more modeling flexibility compared to cliques. We analyze the complexity, general properties, and mathematical programming formulations of the maximum quasi-clique problem. In addition to finding exact optimal solutions, we also present asymptotic bounds on the size of the largest quasi-clique in Erdos-Renyi random graphs. We show that these bounds converge to the classical estimate of the maximum clique size in Erdos-Renyi random graphs, as well as discuss other potential implications of these results.