Premium
On maximum degree‐based γ ‐quasi‐clique problem: Complexity and exact approaches
Author(s) -
Pastukhov Grigory,
Veremyev Alexander,
Boginski Vladimir,
Prokopyev Oleg A.
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21791
Subject(s) - clique problem , degree (music) , vertex (graph theory) , mathematics , clique , cardinality (data modeling) , combinatorics , induced subgraph isomorphism problem , induced subgraph , relaxation (psychology) , clique percolation method , graph , discrete mathematics , computer science , chordal graph , complex network , line graph , acoustics , psychology , social psychology , physics , 1 planar graph , voltage graph , data mining
We consider the problem of finding a degree‐based γ ‐quasi‐clique of maximum cardinality in a given graph for some fixed γ ∈ ( 0 , 1 ] . A degree‐based γ ‐quasi‐clique (often referred to as simply a quasi‐clique) is a subgraph, where the degree of each vertex is at least γ times the maximum possible degree of a vertex in the subgraph. A degree‐based γ ‐quasi‐clique is a relative clique relaxation model, where the case of γ = 1 corresponds to the well‐known concept of a clique. In this article, we first prove that the problem is N P ‐hard for any fixed γ ∈ ( 0 , 1 ] , which addresses one of the open questions in the literature. More importantly, we also develop new exact solution methods for solving the problem and demonstrate their advantages and limitations in extensive computational experiments with both random and real‐world networks. Finally, we outline promising directions of future research including possible functional generalizations of the considered clique relaxation model. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(2), 136–152 2018