Premium
On the analysis of independent sets via multilevel splitting
Author(s) -
Vaisman Radislav,
Kroese Dirk P.
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21805
Subject(s) - counting problem , independent set , time complexity , class (philosophy) , set (abstract data type) , mathematics , optimization problem , computational complexity theory , approximation algorithm , mathematical optimization , computer science , graph , discrete mathematics , combinatorics , algorithm , theoretical computer science , artificial intelligence , programming language
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.