The complexity of choosing an H-colouring (nearly) uniformly at random
The complexity of choosing an H-colouring (nearly) uniformly at random
复制标题
（几乎）随机均匀地选择 H 着色的复杂性
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
M. Paterson
中科院分区：
文献类型：
--
作者：
L. A. Goldberg;S. Kelk;M. Paterson
Cooper、Dyer和Frieze研究了(几乎)均匀随机抽样H-色素的问题。这个问题的特例包括采样着色和独立集，以及来自统计物理模型的采样，如Widom-Rowlinson模型、比奇模型、Potts模型和硬核晶格气体模型。库珀等人。考虑均匀平稳分布的“谨慎”遍历马氏链，证明了对每个固定连通的“非平凡”图H，每个这样的链慢混合.在本文中，我们给出了该问题的一个复杂性结果。也就是说，对于任何没有平凡分支的固定图H，不太可能存在H-着色的多项式几乎一致抽样(PAUS)。我们证明了，如果H-染色问题有一个PAU，那么二部图中抽样独立集也会有一个PAU，并且由于后一个问题的自约性，将会有一个BIS的全多项式随机逼近方案(FPRAS)-二部图中计数独立集的问题。Dyer，Goldberg，Greenhill和Jerrum已经证明了BIS在某个逻辑定义的复杂性类中是完备的。因此，用于采样H-着色的PAU将给出整个复杂性类别的FPRAS。为了达到我们的结果，我们引入了保采样约简的新概念，它在某些情况下似乎比保近似约简更有用。
Cooper, Dyer and Frieze studied the problem of sampling H-colourings (nearly) uniformly at random. Special cases of this problem include sampling colourings 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-colourings. We show that if there were a PAUS for the H-colouring 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 Randomised 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-colourings 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.