#BIS approximability

For two dots joined by an edge, the allowed choices are neither dot, the first dot, or the second dot: three choices in all. Both dots together are forbidden. For any bipartite graph, can a randomized algorithm quickly estimate how many vertex subsets contain no joined pair, to any requested small relative error?[1]

Can the number of legal choices be estimated efficiently even when listing them would be too expensive? On a three-vertex path A–B–C, the choices are the empty set, each of the three single vertices, and {A,C}: five independent sets. Finding the largest choice only finds size two; it does not supply the count five.

For every finite bipartite graph G, let Z(G) count all independent sets, including the empty one. Given $0<\varepsilon<1$, an FPRAS must return $\widehat Z$ in time polynomial in the graph encoding and $1/\varepsilon$, with

$$\Pr[e^{-\varepsilon}Z(G)\leq\widehat Z\leq e^{\varepsilon}Z(G)]\geq3/4.$$

This is the unweighted count: hard-core activity $\lambda=1$ gives each allowed subset weight one. No degree, regularity or expansion promise is part of the target.[1] [2]

Efficient schemes are known under extra regularity, expansion and parameter conditions. They do not cover every bipartite graph with every allowed subset counted equally. The gap concerns estimating all choices, even though finding one largest allowed choice is efficient.[1] [2]

The target is the unweighted count, equivalently hard-core activity λ = 1. Expander algorithms with additional degree/activity conditions do not supply a general FPRAS.[2]

Counting nonconflicting choices in a two-sided graph also helps classify other counting tasks. One is counting choices that obey prerequisite rules: selecting an item can force another to be selected. Established translations preserve efficient estimation with controlled relative error. An efficient scheme for either task would therefore give one for the other, connecting graph exclusions with logical dependencies.[1]

A count can be difficult to compute exactly while still allowing an accurate estimate, so exact counting complexity alone does not settle this question. Approximation-preserving reductions connect #BIS with counting downward-closed subsets of a partial order: choosing an element also requires all smaller elements. They transfer an FPRAS, with its controlled relative error, in both directions. This makes graph exclusions and order constraints part of one approximation classification, letting an algorithm for one representation address the whole established family without requiring exact counts.[1]