AI summaryⓘ
The authors investigate how hard it is to count and sample certain independent sets in bipartite graphs when the sets must have fixed sizes on each side of the graph. They show that if the sizes are balanced in a way that is unusual compared to random graphs, then efficient algorithms likely do not exist unless a major complexity theory breakthrough happens. They also look at a version of the problem where the sizes can vary but must be balanced, showing that the difficulty threshold matches that of a well-studied model (the hard-core model) on bounded-degree graphs. Below a certain parameter value, efficient algorithms exist, but above it, they probably don’t unless widely believed complexity separations collapse.
bipartite graphindependent setfixed-size sliceshard-core modelFPRASefficient samplingphase transitionfugacitycomplexity theorybounded-degree graphs
Authors
Ijay Narang, Will Perkins, Yuzhou Wang, Timothy L. H. Wee
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 $Δ$. The fixed-slice problem asks to sample uniformly from independent sets satisfying $|I\cap L|=α_L n$ and $|I\cap R|=α_R n$. We show that if the overall density $α$ lies in the interval $(\frac{1}Δ, \tfrac{1}{2})$, and the densities on the two sides are more balanced than the typical phase densities of a random $Δ$-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 $λ>0$, the balanced hard-core model is the ordinary hard-core model with fugacity $λ$, 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 $Δ\ge 3$, if $λ<λ_c(Δ)$, then the balanced partition function admits an FPTAS and the balanced hard-core distribution admits an efficient sampling scheme. Conversely, if $λ>λ_c(Δ)$, then no FPRAS or efficient sampler exists on this graph class unless $\mathbf{NP}=\mathbf{RP}$.