Approximately counting H-colourings is #BIS-hard

Approximately counting H-colourings is #BIS-hard

Show other versions (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...

書目詳細資料
Main Authors:	Galanis, A, Goldberg, L, Jerrum, M
格式:	Journal article
出版:	Society for Industrial and Applied Mathematics 2016

相似書籍

Approximately counting H-colourings is BIS-Hard
由: Galanis, A, et al.
出版: (2015)

A complexity trichotomy for approximately counting list H-colourings
由: Goldberg, L, et al.
出版: (2016)

A complexity trichotomy for approximately counting list H-colourings
由: Galanis, A, et al.
出版: (2017)

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
由: Goldberg, L, et al.
出版: (2015)

Approximating pairwise correlations in the Ising model
由: Goldberg, L, et al.
出版: (2019)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
由: Goldberg, L, et al.
出版: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
由: Goldberg, L, et al.
出版: (2016)

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
由: Galanis, A, et al.
出版: (2015)

Inapproximability of counting hypergraph colourings
由: Galanis, A, et al.
出版: (2022)

Approximating the partition function of the ferromagnetic potts model
由: Goldberg, L, et al.
出版: (2012)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs
由: Goldberg, L, et al.
出版: (2016)

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems
由: Galanis, A, et al.
出版: (2017)

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
由: Galanis, A, et al.
出版: (2020)

An approximation trichotomy for Boolean #CSP
由: Dyer, M, et al.
出版: (2010)

Improved hardness for H-colourings of G-colourable graphs
由: Wrochna, M, et al.
出版: (2020)

The complexity of approximately counting retractions
由: Focke, J, et al.
出版: (2019)

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
由: Galanis, A, et al.
出版: (2016)

The complexity of approximately counting retractions
由: Focke, J, et al.
出版: (2020)

Approximately counting locally-optimal structures
由: Goldberg, L, et al.
出版: (2016)

Approximately Counting Locally-Optimal Structures
由: Goldberg, L, et al.
出版: (2015)

Random walks on small world networks
由: Dyer, ME, et al.
出版: (2020)

The complexity of approximately counting retractions to square-free graphs
由: Focke, J, et al.
出版: (2021)

Approximately counting answers to conjunctive queries with disequalities and negations
由: Focke, J, et al.
出版: (2024)

Approximately counting answers to conjunctive queries with disequalities and negations
由: Focke, J, et al.
出版: (2022)

Contiguous cake cutting: Hardness results and approximation algorithms
由: Goldberg, PW, et al.
出版: (2020)

Contiguous cake cutting: hardness results and approximation algorithms
由: Goldberg, PW, et al.
出版: (2020)

The complexity of approximating the complex-valued Potts model
由: Galanis, A, et al.
出版: (2022)

Approximate graph colouring and crystals
由: Ciardo, L, et al.
出版: (2023)

Faster exponential-time algorithms for approximately counting independent sets
由: Goldberg, L, et al.
出版: (2021)

Exact and approximate pattern counting in degenerate graphs: New algorithms, hardness results, and complexity dichotomies
由: Bressan, M, et al.
出版: (2022)

Counting solutions to random CNF formulas
由: Galanis, A, et al.
出版: (2021)

The complexity of approximating the complex-valued Ising model on bounded degree graphs
由: Galanis, A, et al.
出版: (2022)

Approximate graph colouring and the hollow shadow
由: Zivny, S, et al.
出版: (2023)

A complexity classification of spin systems with an external field
由: Goldberg, L, et al.
出版: (2015)

The complexity of approximating the matching polynomial in the complex plane
由: Bezakova, I, et al.
出版: (2021)

Approximate counting and quantum computation
由: Bordewich, M, et al.
出版: (2005)

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
由: Backens, M, et al.
出版: (2019)

Minimal Reachability is Hard to Approximate
由: Jadbabaie, A, et al.
出版: (2023)

Approximate Counting of Graphical Realizations.
由: Péter L Erdős, et al.
出版: (2015-01-01)

Approximation via correlation decay when strong spatial mixing fails
由: Bezakova, I, et al.
出版: (2016)