Inapproximability of the independent set polynomial in the complex plane
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2017
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917242535411712 |
|---|---|
| author | Bezakova, Ivona Galanis, Andreas Goldberg, Leslie Ann Stefankovic, Daniel |
| author_facet | Bezakova, Ivona Galanis, Andreas Goldberg, Leslie Ann Stefankovic, Daniel |
| contents | We study the complexity of approximating the independent set polynomial $Z_G(λ)$ of a graph $G$ with maximum degree $Δ$ when the activity $λ$ is a complex number. This problem is already well understood when $λ$ is real using connections to the $Δ$-regular tree $T$. The key concept in that case is the "occupation ratio" of the tree $T$. This ratio is the contribution to $Z_T(λ)$ from independent sets containing the root of the tree, divided by $Z_T(λ)$ itself. If $λ$ is such that the occupation ratio converges to a limit, as the height of $T$ grows, then there is an FPTAS for approximating $Z_G(λ)$ on a graph $G$ with maximum degree $Δ$. Otherwise, the approximation problem is NP-hard.
Unsurprisingly, the case where $λ$ is complex is more challenging. Peters and Regts identified the complex values of $λ$ for which the occupation ratio of the $Δ$-regular tree converges. These values carve a cardioid-shaped region $Λ_Δ$ in the complex plane. Motivated by the picture in the real case, they asked whether $Λ_Δ$ marks the true approximability threshold for general complex values $λ$.
Our main result shows that for every $λ$ outside of $Λ_Δ$, the problem of approximating $Z_G(λ)$ on graphs $G$ with maximum degree at most $Δ$ is indeed NP-hard. In fact, when $λ$ is outside of $Λ_Δ$ and is not a positive real number, we give the stronger result that approximating $Z_G(λ)$ is actually #P-hard. If $λ$ is a negative real number outside of $Λ_Δ$, we show that it is #P-hard to even decide whether $Z_G(λ)>0$, resolving in the affirmative a conjecture of Harvey, Srivastava and Vondrak. Our proof techniques are based around tools from complex analysis -- specifically the study of iterative multivariate rational maps. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1711_00282 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | Inapproximability of the independent set polynomial in the complex plane Bezakova, Ivona Galanis, Andreas Goldberg, Leslie Ann Stefankovic, Daniel Computational Complexity Discrete Mathematics We study the complexity of approximating the independent set polynomial $Z_G(λ)$ of a graph $G$ with maximum degree $Δ$ when the activity $λ$ is a complex number. This problem is already well understood when $λ$ is real using connections to the $Δ$-regular tree $T$. The key concept in that case is the "occupation ratio" of the tree $T$. This ratio is the contribution to $Z_T(λ)$ from independent sets containing the root of the tree, divided by $Z_T(λ)$ itself. If $λ$ is such that the occupation ratio converges to a limit, as the height of $T$ grows, then there is an FPTAS for approximating $Z_G(λ)$ on a graph $G$ with maximum degree $Δ$. Otherwise, the approximation problem is NP-hard. Unsurprisingly, the case where $λ$ is complex is more challenging. Peters and Regts identified the complex values of $λ$ for which the occupation ratio of the $Δ$-regular tree converges. These values carve a cardioid-shaped region $Λ_Δ$ in the complex plane. Motivated by the picture in the real case, they asked whether $Λ_Δ$ marks the true approximability threshold for general complex values $λ$. Our main result shows that for every $λ$ outside of $Λ_Δ$, the problem of approximating $Z_G(λ)$ on graphs $G$ with maximum degree at most $Δ$ is indeed NP-hard. In fact, when $λ$ is outside of $Λ_Δ$ and is not a positive real number, we give the stronger result that approximating $Z_G(λ)$ is actually #P-hard. If $λ$ is a negative real number outside of $Λ_Δ$, we show that it is #P-hard to even decide whether $Z_G(λ)>0$, resolving in the affirmative a conjecture of Harvey, Srivastava and Vondrak. Our proof techniques are based around tools from complex analysis -- specifically the study of iterative multivariate rational maps. |
| title | Inapproximability of the independent set polynomial in the complex plane |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/1711.00282 |