The Library
Counting and sampling H-colourings
Tools
UNSPECIFIED (2004) Counting and sampling H-colourings. INFORMATION AND COMPUTATION, 189 (1). pp. 1-16. doi:10.1016/j.ic.2003.09.001 ISSN 0890-5401.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.ic.2003.09.001
Abstract
For counting problems in #P which are "essentially self-reducible," it is known that sampling and approximate counting are equivalent. However, many problems of interest do not have such a structure and there is already some evidence that this equivalence does not hold for the whole of #P. An intriguing example is the class of H-colouring problems, which have recently been the subject of much study, and their natural generalisation to vertex- and edge-weighted versions. Particular cases of the counting-to-sampling reduction have been observed, but it has been an open question as to how far these reductions might extend to any H and a general graph G. Here we give the first completely general counting-to-sampling reduction. For every fixed H, we show that the problem of approximately determining the partition function of weighted H-colourings can be reduced to the problem of sampling these colourings from an approximately correct distribution. In particular, any rapidly mixing Markov chain for sampling H-colourings can be turned into an FPRAS for counting H-colourings. (C) 2003 Elsevier Inc. All rights reserved.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | INFORMATION AND COMPUTATION | ||||
Publisher: | ACADEMIC PRESS INC ELSEVIER SCIENCE | ||||
ISSN: | 0890-5401 | ||||
Official Date: | 25 February 2004 | ||||
Dates: |
|
||||
Volume: | 189 | ||||
Number: | 1 | ||||
Number of Pages: | 16 | ||||
Page Range: | pp. 1-16 | ||||
DOI: | 10.1016/j.ic.2003.09.001 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |