Abstract
The maximum independent set (MIS) problem is a well-studied combinatorial optimization problem that naturally arises in many applications, such as wireless communication, information theory and statistical mechanics. MIS problem is NP-hard, thus many results in the literature focus on fast generation of maximal independent sets of high cardinality. One possibility is to combine Gibbs sampling with coupling from the past arguments to detect convergence to the stationary regime. This results in a sampling procedure with time complexity that depends on the mixing time of the Glauber dynamics Markov chain. We propose an adaptive method for random event generation in the Glauber dynamics that considers only the events that are effective in the coupling from the past scheme, accelerating the convergence time of the Gibbs sampling algorithm.
Introduction
The Maximum Independent Set (MIS) problem—identifying a set of vertices in a graph where no two share an edge—is a fundamental NP-hard challenge with broad applications in wireless network scheduling (CSMA), statistical physics, and information theory. Since finding the exact maximum is often computationally intractable, researchers frequently employ Glauber dynamics, a type of Markov Chain Monte Carlo (MCMC) method, to sample independent sets from a Gibbs distribution. By adjusting the 'fugacity' parameter ($\lambda$), the distribution can be biased toward larger independent sets.
To achieve exact sampling from the stationary distribution, Coupling From The Past (CFTP) combined with bounding chains is typically used. However, a significant bottleneck arises at high fugacity: the algorithm rejects most proposed state changes. The simulation spends the majority of its time processing 'passive' events that do not alter the bounding chain, leading to prohibitively slow mixing times. This paper introduces an 'oracle skipping' technique to bypass these passive events without introducing statistical bias.
Methods
The core contribution is the CFTP with Oracle Skipping algorithm. The intuitive goal is to avoid simulating passive events. However, in CFTP, events that are passive when starting from time $-k$ might become active when the simulation window is extended to $-(k+1)$. Simply deleting these events would lead to biased results.
The authors develop a rigorous mathematical framework to handle this, centered on two operations:
- Contraction: The safe removal of passive events (letters) from the sequence.
- Expansion: The probabilistic re-insertion of passive letters according to a geometric distribution based on the active state.
Instead of a linear simulation, the algorithm maintains a queue of active events. When the CFTP window is extended backward, the expansion rules are used to reconstruct the necessary history, ensuring the final sample is perfectly drawn from the target Gibbs distribution. The locality of independent sets—where an event's activity depends only on a vertex and its immediate neighbors—makes this update process computationally efficient.
Results and Key Insights
The proposed method demonstrates significant theoretical and empirical advantages over standard MCMC approaches:
- Theoretical Speedup: On a star graph with $n$ vertices, standard Gibbs sampling has an expected coupling time of $O(\lambda^n)$. Oracle skipping reduces this to $O(n)$, effectively eliminating the exponential dependence on fugacity.
- Empirical Performance: In tests on star graphs (100 and 1000 nodes) and Barabási-Albert random graphs, oracle skipping required orders of magnitude fewer steps than standard Gibbs sampling and consistently outperformed the Dyer-Greenhill scheme.
- Fugacity Independence: Unlike standard MCMC, where higher $\lambda$ increases runtime, oracle skipping's performance is largely independent of $\lambda$. In fact, as $\lambda$ increases, the number of active events often decreases, allowing for even more skipping.
Limitations and Future Work
While oracle skipping drastically reduces the number of simulation steps, it introduces computational overhead for maintaining event queues and calculating expansion probabilities. The current analysis focuses on unweighted graphs, though extensions to weighted cases are possible. Future research aims to apply this technique to queueing networks, which directly model wireless CSMA protocols, where the acceleration of exact sampling could provide significant practical benefits.
Summary updated