Inapproximability of Counting Independent Sets in Linear Hypergraphs

Guoliang Qiu; Jiaheng Wang

doi:10.1016/j.ipl.2023.106448

Inapproximability of Counting Independent Sets in Linear Hypergraphs

Guoliang Qiu, Jiaheng Wang^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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 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 language	English
Article number	106448
Pages (from-to)	1-6
Number of pages	6
Journal	Information Processing Letters
Volume	184
Issue number	February 2024
DOIs	https://doi.org/10.1016/j.ipl.2023.106448
Publication status	Published - 10 Oct 2023

Keywords / Materials (for Non-textual outputs)

Approximate counting
Hypergraph independent set
Linear hypergraph
Inapproximability
approximate algorithm

Access to Document

10.1016/j.ipl.2023.106448Licence: Creative Commons: Attribution (CC-BY)

Inapproximability of counting_QUI_DOA24092023_VOR_CC BYFinal published version, 240 KBLicence: Creative Commons: Attribution (CC-BY)

https://www.sciencedirect.com/science/article/pii/S0020019023000911?via%3DihubLicence: Creative Commons: Attribution (CC-BY)

New Approaches to Counting and Sampling
Guo, H. (Principal Investigator)
EU government bodies
1/01/21 → 31/12/25
Project: Research

Cite this

@article{11dd5f1636824c9a9bc40320bb720b1d,

title = "Inapproximability of Counting Independent Sets in Linear Hypergraphs",

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

keywords = "Approximate counting, Hypergraph independent set, Linear hypergraph, Inapproximability, approximate algorithm",

author = "Guoliang Qiu and Jiaheng Wang",

note = "Funding Information: Jiaheng Wang has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778 ), and an Informatics Global PhD Scholarship at The University of Edinburgh . Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2023",

month = oct,

day = "10",

doi = "10.1016/j.ipl.2023.106448",

language = "English",

volume = "184",

pages = "1--6",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "February 2024",

}

TY - JOUR

T1 - Inapproximability of Counting Independent Sets in Linear Hypergraphs

AU - Qiu, Guoliang

AU - Wang, Jiaheng

N1 - Funding Information: Jiaheng Wang has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778 ), and an Informatics Global PhD Scholarship at The University of Edinburgh . Publisher Copyright: © 2023 The Author(s)

PY - 2023/10/10

Y1 - 2023/10/10

N2 - 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].

AB - 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].

KW - Approximate counting

KW - Hypergraph independent set

KW - Linear hypergraph

KW - Inapproximability

KW - approximate algorithm

U2 - 10.1016/j.ipl.2023.106448

DO - 10.1016/j.ipl.2023.106448

M3 - Article

SN - 0020-0190

VL - 184

SP - 1

EP - 6

JO - Information Processing Letters

JF - Information Processing Letters

IS - February 2024

M1 - 106448

ER -

Inapproximability of Counting Independent Sets in Linear Hypergraphs

Abstract

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

New Approaches to Counting and Sampling

Cite this