{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:19Z","timestamp":1787337559563,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>Cooper, Dyer, and Frieze [J. Algorithms, 39 (2001), pp. 117--134] studied the problem of sampling H-colorings (nearly) uniformly at random. Special cases of this problem include sampling colorings and independent sets and sampling from statistical physics models such as the Widom--Rowlinson model, the Beach model, the Potts model and the hard-core lattice gas model. Cooper et al. considered the family of \"cautious\" ergodic Markov chains with uniform stationary distribution and showed that, for every fixed connected \"nontrivial \" graph H, every such chain mixes slowly. In this paper, we give a complexity result for the problem. Namely, we show that for any fixed graph H with no trivial components, there is unlikely to be any polynomial almost uniform sampler (PAUS) for H-colorings. We show that if there were a PAUS for the H-coloring problem, there would also be a PAUS for sampling independent sets in bipartite graphs, and, by the self-reducibility of the latter problem, there would be a fully polynomial randomized approximation scheme (FPRAS) for #BIS---the problem of counting independent sets in bipartite graphs. Dyer, Goldberg, Greenhill, and Jerrum have shown that #BIS is complete in a certain logically defined complexity class. Thus, a PAUS for sampling H-colorings would give an FPRAS for the entire complexity class. In order to achieve our result we introduce the new notion of sampling-preserving reduction which seems to be more useful in certain settings than approximation-preserving reduction.<\/jats:p>","DOI":"10.1137\/s0097539702408363","type":"journal-article","created":{"date-parts":[[2004,3,5]],"date-time":"2004-03-05T21:00:50Z","timestamp":1078520450000},"page":"416-432","source":"Crossref","is-referenced-by-count":10,"title":["The Complexity of Choosing an\n                    <i>H<\/i>\n                    -Coloring (Nearly) Uniformly at Random"],"prefix":"10.1137","volume":"33","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven","family":"Kelk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mike","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","unstructured":"C. Borgs, J. T. Chayes, M. Dyer, and P. Tetali,\n                      On the sampling problem for H\u2010colorings on the hypercubic lattice\n                      , in Proceedings of the DIMACS\u2010DIMATIA Workshop on Graphs, Homomorphisms and Statistical Physics, J. Nesetril and P. Winkler, eds., AMS, Providence, RI, to appear."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1899"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1142"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Josep D\u00edaz, Maria Serna, Dimitrios Thilikos, (H,C,K)\u2010coloring: fast, easy, and hard cases, Lecture Notes in Comput. Sci., Vol. 2136, Springer, Berlin, 2001, 304\u20133152003d:68095","DOI":"10.1007\/3-540-44683-4_27"},{"key":"R5","unstructured":"J. Diaz, M. Serna, and D. M. Thilikos,\n                      The complexity of parameterized H\u2010colorings\n                      , in Proceedings of the DIMACS\u2010DIMATIA Workshop on Graphs, Homomorphisms and Statistical Physics, J. Nesetril and P. Winkler, eds., AMS, Providence, RI, to appear."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383844"},{"key":"R7","unstructured":"M. Dyer, L. A. Goldberg, and M. Jerrum,\n                      Counting and sampling H\u2010colorings\n                      , Inform. Comput., to appear."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Martin Dyer, Catherine Greenhill, Random walks on combinatorial objects, London Math. Soc. Lecture Note Ser., Vol. 267, Cambridge Univ. Press, Cambridge, 1999, 101\u20131362000h:60073","DOI":"10.1017\/CBO9780511721335.005"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1071"},{"key":"R10","doi-asserted-by":"publisher","unstructured":"Martin Dyer, Catherine Greenhill, The complexity of counting graph homomorphisms, Proceedings of the Ninth International Conference \u201cRandom Structures and Algorithms\u201d (Poznan, 1999), Vol. 17, 2000, 260\u201328910.1002\/1098-2418(200010\/12)17:3\/4<260:AID-RSA5>3.3.CO;2-N2002a:05230","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.3.CO;2-N"},{"key":"R11","unstructured":"M. Dyer, C. Greenhill, L. A. Goldberg, and M. Jerrum,\n                      On the relative complexity of approximate counting problems\n                      , Algorithmica, to appear."},{"key":"R12","unstructured":"M. Dyer, M. Jerrum, and E. Vigoda,\n                      Rapidly mixing Markov chains for dismantleable constraint graphs\n                      , in Proceedings of the DIMACS\/DIMATIA Workshop on Graphs, Morphisms and Statistical Physics, J. Nesetril and P. Winkler, eds., AMS, Providence, RI, 2001, to appear."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00009-1"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070205"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8005-3"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1063\/1.533196"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702408363","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:18Z","timestamp":1787336238000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702408363"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0097539702408363"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702408363","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}