Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs

Abstract

Motivated by recent work of Kocurek, Oveis Gharan, and Tjowasi, which gives an efficient sampling algorithm for the hard-core model on random regular bipartite graphs by decomposing into fixed-size slices, we study the worst-case tractability of approximate counting and sampling of fixed-size slices for bipartite independent set problems. Let $G=(L\sqcup R,E)$ be a bipartite graph with $|L|=|R|=n$ and maximum degree $\Delta$. The fixed-slice problem asks to sample uniformly from independent sets satisfying $|I\cap L|=\alpha_L n$ and $|I\cap R|=\alpha_R n$. We show that if the overall density $\alpha$ lies in the interval $(\frac{1}{\Delta}, \tfrac{1}{2})$, and the densities on the two sides are more balanced than the typical phase densities of a random $\Delta$-regular bipartite graph, then there is no FPRAS or efficient sampling scheme unless $\mathbf{NP}=\mathbf{RP}$. We then study a related fugacity model in which the densities are not fixed, but the independent set is required to be balanced between the two sides of the bipartition. For $\lambda>0$, the balanced hard-core model is the ordinary hard-core model with fugacity $\lambda$, conditioned on the event $|I\cap L|=|I\cap R|$. We prove that this model has the same computational threshold as the hard-core model on general bounded-degree graphs. That is, for every fixed $\Delta\ge 3$, if $\lambda<\lambda_c(\Delta)$, then the balanced partition function admits an FPTAS and the balanced hard-core distribution admits an efficient sampling scheme. Conversely, if $\lambda>\lambda_c(\Delta)$, then no FPRAS or efficient sampler exists on this graph class unless $\mathbf{NP}=\mathbf{RP}$.