Approximately counting H-colourings is #BIS-hard

Approximately counting H-colourings is #BIS-hard

Taispeáin leaganacha eile (1)

We consider the problem of counting H-colourings from an input graph G to a target graph H. 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 gr...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Galanis, A, Goldberg, L, Jerrum, M
Formáid:	Journal article
Foilsithe / Cruthaithe:	Society for Industrial and Applied Mathematics 2016

Míreanna comhchosúla

Approximately counting H-colourings is BIS-Hard
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2015)

A complexity trichotomy for approximately counting list H-colourings
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

A complexity trichotomy for approximately counting list H-colourings
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2017)

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2015)

Approximating pairwise correlations in the Ising model
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2019)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2015)

Inapproximability of counting hypergraph colourings
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2022)

Approximating the partition function of the ferromagnetic potts model
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2012)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2017)

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2020)

An approximation trichotomy for Boolean #CSP
de réir: Dyer, M, et al.
Foilsithe / Cruthaithe: (2010)

Improved hardness for H-colourings of G-colourable graphs
de réir: Wrochna, M, et al.
Foilsithe / Cruthaithe: (2020)

The complexity of approximately counting retractions
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2019)

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of approximately counting retractions
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2020)

Approximately counting locally-optimal structures
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2016)

Approximately Counting Locally-Optimal Structures
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2015)

Random walks on small world networks
de réir: Dyer, ME, et al.
Foilsithe / Cruthaithe: (2020)

The complexity of approximately counting retractions to square-free graphs
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2021)

Approximately counting answers to conjunctive queries with disequalities and negations
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2024)

Approximately counting answers to conjunctive queries with disequalities and negations
de réir: Focke, J, et al.
Foilsithe / Cruthaithe: (2022)

Contiguous cake cutting: Hardness results and approximation algorithms
de réir: Goldberg, PW, et al.
Foilsithe / Cruthaithe: (2020)

Contiguous cake cutting: hardness results and approximation algorithms
de réir: Goldberg, PW, et al.
Foilsithe / Cruthaithe: (2020)

The complexity of approximating the complex-valued Potts model
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2022)

Approximate graph colouring and crystals
de réir: Ciardo, L, et al.
Foilsithe / Cruthaithe: (2023)

Faster exponential-time algorithms for approximately counting independent sets
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2021)

Exact and approximate pattern counting in degenerate graphs: New algorithms, hardness results, and complexity dichotomies
de réir: Bressan, M, et al.
Foilsithe / Cruthaithe: (2022)

Counting solutions to random CNF formulas
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2021)

The complexity of approximating the complex-valued Ising model on bounded degree graphs
de réir: Galanis, A, et al.
Foilsithe / Cruthaithe: (2022)

Approximate graph colouring and the hollow shadow
de réir: Zivny, S, et al.
Foilsithe / Cruthaithe: (2023)

A complexity classification of spin systems with an external field
de réir: Goldberg, L, et al.
Foilsithe / Cruthaithe: (2015)

The complexity of approximating the matching polynomial in the complex plane
de réir: Bezakova, I, et al.
Foilsithe / Cruthaithe: (2021)

Approximate counting and quantum computation
de réir: Bordewich, M, et al.
Foilsithe / Cruthaithe: (2005)

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
de réir: Backens, M, et al.
Foilsithe / Cruthaithe: (2019)

Minimal Reachability is Hard to Approximate
de réir: Jadbabaie, A, et al.
Foilsithe / Cruthaithe: (2023)

Approximate Counting of Graphical Realizations.
de réir: Péter L Erdős, et al.
Foilsithe / Cruthaithe: (2015-01-01)

Approximation via correlation decay when strong spatial mixing fails
de réir: Bezakova, I, et al.
Foilsithe / Cruthaithe: (2016)