Inapproximability of Counting Independent Sets in Linear Hypergraphs

2022/12/06 by Guoliang Qiu, Qiu, Guoliang, Jiaheng Wang +1 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2212.03072

openalex publication_date 2022/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 Δ≥ 5⋅ 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).

Cited by

• Learning CNF formulas from uniform random solutions in the local lemma regime

Related

• Faster Exponential-time Algorithms for Approximately Counting\n Independent Sets
• Approximately counting maximal independent set is equivalent to #SAT
• A Perfect Sampler for Hypergraph Independent Sets
• Counting hypergraph colorings in the local lemma regime
• Approximate Counting of Matchings in Sparse Uniform Hypergraphs