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\bigsqcup R,E)$ be a bipartite graph with $|L|=|R|=n$ and maximum degree $\hat{I}”$. The fixed-slice problem asks to sample uniformly from independent sets satisfying $|I\cap L|=\hat{I}{\pm }_{L}n$ and $|I\cap R|=\hat{I}{\pm }_{R}n$. We show that if the overall density $\hat{I}\pm$ lies in the interval $(\frac{1}{\hat{I}}”,\frac{1}{2})$, and the densities on the two sides are more balanced than the typical phase densities of a random $\hat{I}”$-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 $\hat{I}»>0$, the balanced hard-core model is the ordinary hard-core model with fugacity $\hat{I}»$, 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 $\hat{I}”\ge 3$, if $\hat{I}»<\hat{I}{»}_c(\hat{I}”)$, then the balanced partition function admits an FPTAS and the balanced hard-core distribution admits an efficient sampling scheme. Conversely, if $\hat{I}»>\hat{I}{»}_c(\hat{I}”)$, then no FPRAS or efficient sampler exists on this graph class unless $\mathbf{NP}=\mathbf{RP}$.