Implementations and the independent set polynomial below the Shearer threshold
The independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer ≥ 2, the Shearer threshold is the value λ∗() = ( − 1)−1/. It is known that for λ < −λ∗(), there are graphs G with maximum degree whose independent set polynom...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2022
|
| _version_ | 1797108484203872256 |
|---|---|
| author | Galanis, A Goldberg, L Stefankovic, D |
| author_facet | Galanis, A Goldberg, L Stefankovic, D |
| author_sort | Galanis, A |
| collection | OXFORD |
| description | The independent set polynomial is important in many areas of combinatorics, computer
science, and statistical physics. For every integer ≥ 2, the Shearer threshold is the
value λ∗() = ( − 1)−1/. It is known that for λ < −λ∗(), there are graphs G
with maximum degree whose independent set polynomial, evaluated at λ, is at
most 0. Also, there are no such graphs for any λ > −λ∗(). This paper is motivated
by the computational problem of approximating the independent set polynomial when
λ < −λ∗(). The key issue in complexity bounds for this problem is “implementation”.
Informally, an implementation of a real number λ� is a graph whose hard-core partition
function, evaluated at λ, simulates a vertex-weight of λ� in the sense that λ� is the
ratio between the contribution to the partition function from independent sets containing
a certain vertex and the contribution from independent sets that do not contain that
vertex. Implementations are the cornerstone of intractability results for the problem of
approximately evaluating the independent set polynomial. Our main result is that, for any
λ < −λ∗(), it is possible to implement a set of values that is dense over the reals. The
result is tight in the sense that it is not possible to implement a set of values that is
dense over the reals for any λ > λ∗(). Our result has already been used in a paper with
Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the
independent set polynomial on graphs of degree at most at any value λ < −λ∗(). In
the appendix, we give an additional incomparable inapproximability result (strengthening
the inapproximability bound to an exponential factor, but weakening the hardness to NPhardness). |
| first_indexed | 2024-03-07T07:28:25Z |
| format | Journal article |
| id | oxford-uuid:1d19577d-8afa-4c86-a8ca-5da9bc779ba6 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:28:25Z |
| publishDate | 2022 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:1d19577d-8afa-4c86-a8ca-5da9bc779ba62022-12-22T12:11:46ZImplementations and the independent set polynomial below the Shearer thresholdJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:1d19577d-8afa-4c86-a8ca-5da9bc779ba6EnglishSymplectic ElementsElsevier2022Galanis, AGoldberg, LStefankovic, DThe independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer ≥ 2, the Shearer threshold is the value λ∗() = ( − 1)−1/. It is known that for λ < −λ∗(), there are graphs G with maximum degree whose independent set polynomial, evaluated at λ, is at most 0. Also, there are no such graphs for any λ > −λ∗(). This paper is motivated by the computational problem of approximating the independent set polynomial when λ < −λ∗(). The key issue in complexity bounds for this problem is “implementation”. Informally, an implementation of a real number λ� is a graph whose hard-core partition function, evaluated at λ, simulates a vertex-weight of λ� in the sense that λ� is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any λ < −λ∗(), it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any λ > λ∗(). Our result has already been used in a paper with Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most at any value λ < −λ∗(). In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NPhardness). |
| spellingShingle | Galanis, A Goldberg, L Stefankovic, D Implementations and the independent set polynomial below the Shearer threshold |
| title | Implementations and the independent set polynomial below the Shearer threshold |
| title_full | Implementations and the independent set polynomial below the Shearer threshold |
| title_fullStr | Implementations and the independent set polynomial below the Shearer threshold |
| title_full_unstemmed | Implementations and the independent set polynomial below the Shearer threshold |
| title_short | Implementations and the independent set polynomial below the Shearer threshold |
| title_sort | implementations and the independent set polynomial below the shearer threshold |
| work_keys_str_mv | AT galanisa implementationsandtheindependentsetpolynomialbelowtheshearerthreshold AT goldbergl implementationsandtheindependentsetpolynomialbelowtheshearerthreshold AT stefankovicd implementationsandtheindependentsetpolynomialbelowtheshearerthreshold |