95 citations · 675 across the 48 of their papers we have counts for
5 papers · 2 filters
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg +4
Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an…
Some hard families of parameterised counting problems
Mark Jerrum, Kitty Meeks
We consider parameterised subgraph-counting problems of the following form: given a graph G, how many k-tuples of its vertices have a given property? A number of such problems are…
The complexity of parity graph homomorphism: an initial investigation
John Faben, Mark Jerrum
Given a graph G, we investigate the question of determining the parity of the number of homomorphisms from G to some other fixed graph H. We conjecture that this problem exhibits a…
The Parameterised Complexity of Counting Connected Subgraphs and Graph Motifs
Mark Jerrum, Kitty Meeks
We introduce a class of parameterised counting problems on graphs, p-#Induced Subgraph With Property(Φ), which generalises a number of problems which have previously been studied.…
The Complexity of Approximately Counting Tree Homomorphisms
Leslie Ann Goldberg, Mark Jerrum
We study two computational problems, parameterised by a fixed tree H. #HomsTo(H) is the problem of counting homomorphisms from an input graph G to H. #WHomsTo(H) is the problem of…