On Maximal Subgraph Sampling via Proximity Search

Graphs are fundamentally binary relations over finite sets. When working with a graph, a common approach involves studying specific combinatorial structures within it, such as cliques, independent sets, and bipartite subgraphs. The sampling problem over a combinatorial structure aims to address the question “Can one of these be generated uniformly at random?”. This thesis proposes a novel solution to the sampling problem for combinatorial structures within graphs. The sampling method we will focus on is Markov Chain Monte Carlo (MCMC). The core challenge lies in constructing a Markov chain over the solution space such that its stationary distribution aligns with the desired sampling distribution. The distribution of the Markov chain converges to the stationary one, thereby enabling us to sample in an approximate manner from our target distribution. Many frameworks designed for the enumeration problem, such as Reverse Search by Avis & Fukuda and Proximity Search by Conte & Uno, consist in building a connected graph (the solution graph) over the solution space and exploring it. In this thesis, we consider the use of a random walk on this solution graph as a potential Markov chain for sampling via MCMC. In doing so, several challenges and questions emerge: Firstly, regarding the algorithm's correctness, the stationary distribution of the random walk does not reflect the desired sampling distribution. Adapting the walk to our desired distribution can be achieved via the Metropolis algorithm. Secondly, from an efficiency standpoint, the time it takes for the Markov chain to `mix' also needs to be within polynomial bounds. Our objective is to prove that this condition is satisfied.