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

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.

V2: The most important change is that we modified the statement of Lemma 5.3 and added proof (as the previous version was flawed; see Remark 5.4). Next to that we fixed some typos and other small things. The main results have not changed