TY - JOUR
T1 - On inclusionwise maximal and maximum cardinality k-clubs in graphs
AU - Mahdavi Pajouh, F.
AU - Balasundaram, B.
PY - 2012/5
Y1 - 2012/5
N2 - A k-club is a distance-based graph-theoretic generalization of a clique, originally introduced to model cohesive social subgroups in social network analysis. The k-clubs represent low diameter clusters in graphs and are appropriate for various graph-based data mining applications. Unlike cliques, the k-club model is nonhereditary, meaning every subset of a k-club is not necessarily a k-club. In this article, we settle an open problem establishing the intractability of testing inclusion-wise maximality of k-clubs. This result is in contrast to polynomial-time verifiability of maximal cliques, and is a direct consequence of its nonhereditary nature. We also identify a class of graphs for which this problem is polynomial-time solvable. We propose a distance coloring based upper-bounding scheme and a bounded enumeration based lower-bounding routine and employ them in a combinatorial branch-and-bound algorithm for finding maximum cardinality k-clubs. Computational results from using the proposed algorithms on 200-vertex graphs are also provided.
AB - A k-club is a distance-based graph-theoretic generalization of a clique, originally introduced to model cohesive social subgroups in social network analysis. The k-clubs represent low diameter clusters in graphs and are appropriate for various graph-based data mining applications. Unlike cliques, the k-club model is nonhereditary, meaning every subset of a k-club is not necessarily a k-club. In this article, we settle an open problem establishing the intractability of testing inclusion-wise maximality of k-clubs. This result is in contrast to polynomial-time verifiability of maximal cliques, and is a direct consequence of its nonhereditary nature. We also identify a class of graphs for which this problem is polynomial-time solvable. We propose a distance coloring based upper-bounding scheme and a bounded enumeration based lower-bounding routine and employ them in a combinatorial branch-and-bound algorithm for finding maximum cardinality k-clubs. Computational results from using the proposed algorithms on 200-vertex graphs are also provided.
KW - Clique
KW - Exact combinatorial algorithms
KW - Graph-based data mining
KW - Social network analysis
KW - k-club
UR - http://www.scopus.com/inward/record.url?scp=84860514572&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860514572&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2012.02.002
DO - 10.1016/j.disopt.2012.02.002
M3 - Article
AN - SCOPUS:84860514572
SN - 1572-5286
VL - 9
SP - 84
EP - 97
JO - Discrete Optimization
JF - Discrete Optimization
IS - 2
ER -