A fixed-parameter perspective on #BIS by Curticapean, R, Dell, H, Fomin, F, Goldberg, L, Lapinskas, J

“…The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHΠ1. …”

A fixed-parameter perspective on #BIS by Curticapean, R, Dell, H, Fomin, F, Goldberg, L, Lapinskas, J

“…The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHΠ1. …”

Approximately counting locally-optimal structures by Goldberg, L, Gysel, R, Lapinskas, J

“…Assuming that #BIS is not equivalent to #SAT under AP-reductions, we show that counting maximal independent sets in bipartite graphs is harder than counting maximum independent sets. …”

Faster exponential-time algorithms for approximately counting independent sets by Goldberg, L, Lapinskas, J, Richerby, D

“…The running time of our algorithm on general graphs with error tolerance ε is at most O(20.2680n) times a polynomial in 1/ε. On bipartite graphs, the exponential term in the running time is improved to O(20.2372n). …”

Approximately Counting Locally-Optimal Structures by Goldberg, L, Gysel, R, Lapinskas, J

“…Motivated by the difficulty of approximately counting maximal independent sets in bipartite graphs, we also study counting problems involving minimal separators and minimal edge separators (which are also locally-optimal structures). …”