On inclusionwise maximal and maximum cardinality k-clubs in graphs

F. Mahdavi Pajouh, B. Balasundaram

Research output: Contribution to journalArticlepeer-review

51 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)84-97
Number of pages14
JournalDiscrete Optimization
Volume9
Issue number2
DOIs
StatePublished - May 2012

Keywords

  • Clique
  • Exact combinatorial algorithms
  • Graph-based data mining
  • Social network analysis
  • k-club

Fingerprint

Dive into the research topics of 'On inclusionwise maximal and maximum cardinality k-clubs in graphs'. Together they form a unique fingerprint.

Cite this