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. …”

Counting edge-injective homomorphisms and matchings on restricted graph classes by Curticapean, R, Dell, H, Roth, M

“…We consider the #W[1]-hard problem of counting all matchings with exactly k edges in a given input graph G; we prove that it remains #W[1]-hard on graphs G that are line graphs or bipartite graphs with degree 2 on one side. In our proofs, we use that k-matchings in line graphs can be equivalently viewed as edge-injective homomorphisms from the disjoint union of k length-2 paths into (arbitrary) host graphs. …”

Fine-grained dichotomies for the Tutte plane and Boolean #CSP by Roth, M, Brand, C, Dell, H

“…The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time exp(o(n)) unless #ETH fails.…”

Fine-grained dichotomies for the Tutte Plane and Boolean #CSP by Brand, C, Dell, H, Roth, M

“…The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time Open image in new window unless #ETH fails. …”