An exact algorithm for the maximum probabilistic clique problem

Zhuqi Miao, Balabhaskar Balasundaram, Eduardo L. Pasiliao

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.

Original languageEnglish
Pages (from-to)105-120
Number of pages16
JournalJournal of Combinatorial Optimization
Volume28
Issue number1
DOIs
StatePublished - 1 Jan 2014
Externally publishedYes

Keywords

  • Branch-and-bound
  • Maximum clique problem
  • Probabilistic clique
  • Probabilistic programming

Fingerprint Dive into the research topics of 'An exact algorithm for the maximum probabilistic clique problem'. Together they form a unique fingerprint.

Cite this