On the complex zeros and the computational complexity of approximating the reliability polynomial

2025/12/12 by Bencs, Ferenc, Piombi, Chiara, Regts, Guus
Computer Science · Engineering · Mathematics · #5C31 primary #68W25 secondary #82B20 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #Reliability and Maintenance Optimization

paper · doi:10.48550/arxiv.2512.11504

openalex publication_date 2025/12/12 · openalex created_date 2025/12/16 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Approximating the chromatic polynomial is as hard as computing it exactly
• On the location of chromatic zeros of series-parallel graphs
• The complexity of approximating the complex-valued Ising model on bounded degree graphs
• Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
• Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• The complexity of approximating the complex-valued Potts model
• The complexity of approximating the matching polynomial in the complex plane
• Inapproximability of the independent set polynomial in the complex plane
• A Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem
• Factoring polynomials with rational coefficients

Related

• Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
• On the Reliability Roots of Simplicial Complexes and Matroids
• Zeros of reliability polynomials and f-vectors of matroids
• Reliability Polynomials of Simple Graphs having Arbitrarily many Inflection Points
• All Terminal Reliability Roots of Smallest Modulus