Inapproximability of counting independent sets in linear hypergraphs

DOI10.1016/J.IPL.2023.106448MaRDI QIDQ6121429zbMATH OpenOpenAlexFDO

Authors Guoliang Qiu, Jiaheng Wang

Publication date 26 March 2024

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2212.03072

zbMATH Keywords

approximate countingapproximation algorithmshypergraph independent setinapproximabilitylinear hypergraph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 $Delta$ is NP-hard if $Deltageq5cdot{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 (2019), the perfect sampler by Qiu, Wang and Zhang (2022), and the deterministic approximation scheme by Feng, Guo, Wang, Wang and Yin (2022).

Cites work

• A constructive proof of the general Lovász local lemma
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Counting in two-spin models on \(d\)-regular graphs
• Fast mixing for independent sets, colorings, and other models on trees
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Random generation of combinatorial structures from a uniform distribution
• Rapid mixing of hypergraph independent sets
• Stopping Times, Metrics and Approximate Counting

Cited in

(1)

• Toward derandomizing Markov chain Monte Carlo

This page was built for publication: Inapproximability of counting independent sets in linear hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6121429)