On the analysis of independent sets via multilevel splitting
Radislav Vaisman, Dirk P. Kroese · Networks · 2018
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.