论文标题
在线性超图中计数独立集的不适当性
Inapproximability of Counting Independent Sets in Linear Hypergraphs
论文作者
论文摘要
本说明中显示的是，如果$δ\ geq 5 \ geq 5 \ cdot 2^{k-1}+1 $，则近似于$ k $均匀的线性超图（最多$δ$）的独立集数为np-hard。这证实，对于相关的采样和近似计数问题，最大程度的最大程度的制度是紧密的，最多是一些小因素。这些算法包括：Hermon，Sly和Zhang（RSA，2019年）的近似采样器和随机近似方案，Qiu，Wang和Zhang的Perfect Sampler（ICALP，2022），以及Feng，Guo，Guo，Guo，Guo，Guo，Guo，Guo，guo，guo，wang，wang，wang and yin（pocs，20223）的确定性近似方案。
It is shown in this note that approximating the number of independent sets in a $k$-uniform linear hypergraph with maximum degree at most $Δ$ is NP-hard if $Δ\geq 5\cdot 2^{k-1}+1$. This confirms that for the relevant sampling and approximate counting problems, the regimes on the maximum degree where the state-of-the-art algorithms work are tight, up to some small factors. These algorithms include: the approximate sampler and randomised approximation scheme by Hermon, Sly and Zhang (RSA, 2019), the perfect sampler by Qiu, Wang and Zhang (ICALP, 2022), and the deterministic approximation scheme by Feng, Guo, Wang, Wang and Yin (FOCS, 2023).
