On the analysis of independent sets via multilevel splitting

Vaisman, Radislav and Kroese, Dirk P. (2018) On the analysis of independent sets via multilevel splitting. Networks, 71 3: 281-301. doi:10.1002/net.21805

Author Vaisman, Radislav
Kroese, Dirk P.
Title On the analysis of independent sets via multilevel splitting
Journal name Networks   Check publisher's open access policy
ISSN 1097-0037
Publication date 2018-01-10
Sub-type Article (original research)
DOI 10.1002/net.21805
Open Access Status Not yet assessed
Volume 71
Issue 3
Start page 281
End page 301
Total pages 21
Place of publication Hoboken, NJ, United States
Publisher John Wiley & Sons
Language eng
Subject 1712 Software
1710 Information Systems
1708 Hardware and Architecture
1705 Computer Networks and Communications
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.
Keyword Counting problem
Independent sets
Markov chain Monte Carlo
Multilevel splitting
Sequential importance sampling
Q-Index Code C1
Q-Index Status Provisional Code
Grant ID CE140100049
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
HERDC Pre-Audit
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Fri, 12 Jan 2018, 01:46:46 EST by Radislav Vaisman on behalf of Mathematics