Inapproximability of Counting Independent Sets in Linear Hypergraphs

Guoliang Qiu, Jiaheng Wang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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 et al. (2019) [5], the perfect sampler by Qiu et al. (2022) [6], and the deterministic approximation scheme by Feng et al. (2023) [7].

Original languageEnglish
Article number106448
Pages (from-to)1-6
Number of pages6
JournalInformation Processing Letters
Volume184
Issue numberFebruary 2024
DOIs
Publication statusPublished - 10 Oct 2023

Keywords / Materials (for Non-textual outputs)

  • Approximate counting
  • Hypergraph independent set
  • Linear hypergraph
  • Inapproximability
  • approximate algorithm

Fingerprint

Dive into the research topics of 'Inapproximability of Counting Independent Sets in Linear Hypergraphs'. Together they form a unique fingerprint.

Cite this