Inapproximability of counting independent sets in linear hypergraphs

DOI10.1016/j.ipl.2023.106448arXiv2212.03072OpenAlexW4387167299MaRDI QIDQ6121429

Guoliang Qiu, Jiaheng Wang

Publication date: 26 March 2024

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

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

zbMATH Keywords

linear hypergraphapproximation algorithmsinapproximabilityapproximate countinghypergraph independent set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Counting in two-spin models on \(d\)-regular graphs
• Random generation of combinatorial structures from a uniform distribution
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• A constructive proof of the general lovász local lemma
• Stopping Times, Metrics and Approximate Counting
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Rapid mixing of hypergraph independent sets
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Fast mixing for independent sets, colorings, and other models on trees

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