Name
Abstract | ||
|---|---|---|
We consider counting H-colourings from an input graph G to a target graph H. We show that for any fixed graph H 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. If this is so, then our result shows that for every graph H without trivial components, the H-colouring counting problem has no FPRAS. This problem was studied a decade ago by Goldberg, Kelk and Paterson. They were able to show that approximately sampling H-colourings is #BIS-hard, but it was not known how to get the result for approximate counting. Our solution builds on non-constructive ideas using the work of Lovasz. The full version is available at arxiv.org/abs/1502.01335. The theorem numbering here matches the full version. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-662-47672-7_43 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Complexity class,Numbering,Complete bipartite graph,Discrete mathematics,Graph,Combinatorics,Computer science,Bipartite graph,Counting problem,Sampling (statistics) | Journal | 9134 |
Issue | ISSN | Citations |
3 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| andreas galanis | 1 | 68 | 15.13 |
| leslie ann goldberg | 2 | 1411 | 125.20 |
| mark jerrum | 3 | 2755 | 564.62 |