On the analysis of independent sets via multilevel splitting. Issue 3 (10th January 2018)

• Record Type: Journal Article
• Authors: Vaisman, Radislav; Kroese, Dirk P.
• Is Part Of: Networks. Volume 71:Issue 3(2018)
• Page Start: 281
• Page End: 301
• Publication Date: 2018-01-10
• Subjects: counting problem -- independent sets -- Markov chain Monte Carlo -- multilevel splitting -- networks -- rare‐event simulation -- sequential importance sampling; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21805
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : Counting the number of independent sets is an important problem in graph theory, combinatorics, optimization, and social sciences. However, a polynomial‐time exact calculation, or even a reasonably close approximation, is widely believed to be impossible, since their existence implies an efficient solution to various problems in the non‐deterministic polynomial‐time complexity class. To cope with the approximation challenge, we express the independent set counting problem as a rare‐event estimation problem. We develop a multilevel splitting algorithm which is generally capable of delivering accurate results, while using a manageable computational effort, even when applied to large graphs. We apply the algorithm to both counting and optimization (finding a maximum independent set) problems, and show that it compares favorably with the existing state of the art.