The complexity of approximately counting stable matchings
- 作者：Prasad Chebolu ; Leslie Ann Goldberg ; Russell Martin ; Russell.Martin@liverpool.ac.uk
- 关键词：Stable marriage problem ; Approximation-preserving reduction ; Counting independent sets in bipartite graphs (#BIS)
- 刊名：Theoretical Computer Science
- 出版年：2012
- 期刊代码：114_03043975
- 类别：cp
- 出版时间：15 June, 2012
- 卷：437
- 期：Complete
- 页码：35-68
- 文件大小：420 K
摘要
We investigate the complexity of approximately counting stable matchings in the -attribute model, where the preference lists are determined by dot products of 鈥減reference vectors鈥?with 鈥渁ttribute vectors鈥? or by Euclidean distances between 鈥減reference points 鈥渁nd 鈥渁ttribute points鈥? Irving and Leather (1986)聽 proved that counting the number of stable matchings in the general case is -complete. Counting the number of stable matchings is reducible to counting the number of downsets in a (related) partial order聽 and is interreducible, in an approximation-preserving sense, to a class of problems that includes counting the number of independent sets in a bipartite graph ()聽(Dyer et聽al. (2004)聽). It is conjectured that no FPRAS exists for this class of problems. We show this approximation-preserving interreducibility remains even in the restricted -attribute setting when (dot products) or (Euclidean distances). Finally, we show it is easy to count the number of stable matchings in the -attribute dot-product setting.