Counting and sampling H-colourings
UNSPECIFIED. (2004) Counting and sampling H-colourings. INFORMATION AND COMPUTATION, 189 (1). pp. 1-16. ISSN 0890-5401Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.ic.2003.09.001
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|
|Date:||25 February 2004|
|Number of Pages:||16|
|Page Range:||pp. 1-16|
Actions (login required)