Approximate Counting of Matchings in (3, 3)-Hypergraphs
Approximate Counting of Matchings in (3, 3)-Hypergraphs
复制标题
(3, 3)-超图中匹配的近似计数
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Edyta Szymanska
中科院分区：
文献类型：
--
作者：
A. Dudek;Marek Karpinski;A. Rucinski;Edyta Szymanska
我们设计了一个完全多项式时间近似方案（FPTAS），用于计算最大次数为 3 的任意 3-一致超图（称为 $(3,3)$-超图）中的匹配（打包）数量。这是该问题的第一个多项式时间近似方案，作为特例，它还包括 3 部分 $(3,3)$ 超图的 3D 匹配计数问题。本文的证明技术使用了一般相关衰减技术和对交图基础结构的新组合分析。证明方法也可能具有独立的意义。
We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting problem for 3-partite $(3,3)$-hypergraphs. The proof technique of this paper uses the general correlation decay technique and a new combinatorial analysis of the underlying structures of the intersection graphs. The proof method could be also of independent interest.