A complexity trichotomy for approximately counting list H-colourings by Goldberg, L, Galanis, A, Jerrum, M

“…If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. …”

A complexity trichotomy for approximately counting list H-colourings by Galanis, A, Goldberg, L, Jerrum, M

“…If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. …”

Approximately counting H-colourings is BIS-Hard by Galanis, A, Goldberg, L, Jerrum, M

“…We show that for any fixed graph <em>H</em> without trivial components, this is as hard as the well-known problem #BIS, the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in an important complexity class for approximate counting, and is believed not to have an FPRAS. …”

Approximately counting H-colourings is #BIS-hard by Galanis, A, Goldberg, L, Jerrum, M

“…We show that if H is any fixed graph without trivial components, then the problem is as hard as the well-known problem #BIS, which is the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in a important complexity class for approximate counting, and is believed not to have an FPRAS. …”

The complexity of counting locally maximal satisfying assignments of Boolean CSPs by Goldberg, L, Jerrum, M

“…This finding contrasts with the recent discovery that approximately counting locally maximal independent sets in a bipartite graph is harder (under the usual complexity-theoretic assumptions) than counting all independent sets.…”

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

The complexity of approximately counting retractions by Focke, J, Goldberg, L, Zivny, S

“…The result is as follows: (1) Approximately counting retractions to a tree H is in FP if H is a star, a single looped vertex, or an edge with two loops. (2) Otherwise, if H is an irreflexive caterpillar or a partially bristled reflexive path, then approximately counting retractions to H is equivalent to approximately counting the independent sets of a bipartite graph — a problem which is complete in the approximate counting complexity class RHπ1. (3) Finally, if none of these hold, then approximately counting retractions to H is #P-complete under approximation-preserving reductions. …”

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region by Goldberg, L, Galanis, A, Cai, J, Guo, H, Jerrum, M, Stefankovic, D, Vigoda, E

“…Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. …”

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems by Galanis, A, Goldberg, L, Yang, K

“…Our main result shows that: (i) if every function in &Gamma; is affine, then #CSP∆(&Gamma;) is in FP for all ∆, (ii) otherwise, if every function in &Gamma; is in a class called IM2, then for large ∆, #CSP∆(&Gamma;) is equivalent under approximation-preserving reductions to the problem of counting independent sets in bipartite graphs, (iii) otherwise, for large ∆, it is NP-hard to approximate #CSP∆(&Gamma;), even within an exponential factor.…”

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

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems by Galanis, A, Goldberg, L, Yang, K

“…Our main result shows that: (i) if every function in Γ is affine, then #CSPΔ(Γ) is in FP for all Δ, (ii) otherwise, if every function in Γ is in a class called IM2, then for all sufficiently large Δ, #CSPΔ(Γ) is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large Δ, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSPΔ(Γ), even within an exponential factor. …”

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