On the complex zeros and the computational complexity of approximating the reliability polynomial
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917234165678080 |
|---|---|
| author | Bencs, Ferenc Piombi, Chiara Regts, Guus |
| author_facet | Bencs, Ferenc Piombi, Chiara Regts, Guus |
| contents | In this paper we relate the location of the complex zeros of the reliability polynomial to parameters at which a certain family of rational functions derived from the reliability polynomial exhibits chaotic behaviour. We use this connection to prove new results about the location of reliability zeros. In particular we show that there are zeros with modulus larger than $1$ with essentially any possible argument. We moreover use this connection to show that approximately evaluating the reliability polynomial for planar graphs at a non-positive algebraic number in the unit disk is #P-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11504 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the complex zeros and the computational complexity of approximating the reliability polynomial Bencs, Ferenc Piombi, Chiara Regts, Guus Combinatorics Computational Complexity Discrete Mathematics 5C31 primary, 82B20, 68W25 secondary In this paper we relate the location of the complex zeros of the reliability polynomial to parameters at which a certain family of rational functions derived from the reliability polynomial exhibits chaotic behaviour. We use this connection to prove new results about the location of reliability zeros. In particular we show that there are zeros with modulus larger than $1$ with essentially any possible argument. We moreover use this connection to show that approximately evaluating the reliability polynomial for planar graphs at a non-positive algebraic number in the unit disk is #P-hard. |
| title | On the complex zeros and the computational complexity of approximating the reliability polynomial |
| topic | Combinatorics Computational Complexity Discrete Mathematics 5C31 primary, 82B20, 68W25 secondary |
| url | https://arxiv.org/abs/2512.11504 |