On the hardness of finding balanced independent sets in random bipartite graphs

We consider the algorithmic problem of finding large balanced independent sets in sparse random bipartite graphs, and more generally the problem of finding independent sets with specified proportions of vertices on each side of the bipartition. In a bipartite graph it is trivial to find an independent set of density at least half (take one of the partition classes). In contrast, in a random bipartite graph of average degree d, the largest balanced independent sets (containing equal number of vertices from each class) are typically of density (2 + o d (1)) log d d . Can we find such large balanced independent sets in these graphs efficiently? By utilizing the overlap gap property and the low-degree algorithmic framework, we prove that local and low-degree algorithms (even those that know the bipartition) cannot find balanced independent sets of density greater than (1 + ε) log d d for any ε > 0 fixed and d large but constant. This factor 2 statistical-computational gap between what exists and what local algorithms can achieve is analogous to the gap for finding large independent sets in (non-bipartite) random graphs. Our results therefor suggest that this gap is pervasive in many models, and that hard computational problems can lurk inside otherwise tractable ones. A particularly striking aspect of the gap in bipartite graphs is that the algorithm achieving the lower bound is extremely simple and can be implemented as a 1-local algorithm and a degree-1 polynomial (a linear function).

More generally, we provide a tight characterization of the power of local and low-degree algorithms to find γ-balanced independent sets in random d-regular bipartite graphs (with γ ≤ 1/2 proportion of vertices on one side of the partition): for large d, local algorithms can find γ-balanced independent sets a factor (1 -γ) smaller than those that exist whp in random bipartite graphs, and no larger.