The complexity of counting colourings and independent sets in sparse graphs and hypergraphs |
| |
Authors: | C. Greenhill |
| |
Affiliation: | (1) School of Computer Studies, University of Leeds, Leeds, LS2 9JT, U.K., e-mail: csg@scs.leeds.ac.uk , GB |
| |
Abstract: | We consider certain counting problems involving colourings of graphs and independent sets in hypergraphs. Using polynomial interpolation techniques, we show that these problems are #P-complete. Therefore, efficient approximate counting is the most one can realistically expect to achieve. Rapidly mixing Markov chains which can be used for approximately solving some of these counting problems have been recently developed by the author and others. Received: June 19, 1998. |
| |
Keywords: | . Graph colourings independent sets #P-completeness interpolation. |
本文献已被 SpringerLink 等数据库收录! |
|