The complexity of the reliable connectivity problem

Let G=(V,E) be a graph together with two distinguished nodes s and t, and suppose that to every node f(v)∈V, a nonnegative integer f(v)≤degree(v) is assigned. Suppose, moreover, that each node υ can cause at most f(v) of its incident edges to "fail" (these f(v) edges can be arbitrarily chosen). The Reliable Connectivity Problem is to test whether node s remains connected to t by a path of non-failed edges for all possible choices of the failed edges. Although, as expected, the general Reliable Connectivity Problem is co-NP-complete and this remains true even if G is restricted to the class of directed, acyclic graphs, we show that the problem is in P for directed, acyclic graphs if the edges caused to fail by each node υ are chosen only from the edges incoming to v. Concerning the parallel complexity of the latter version of the problem, it turns out that it is P-complete. Moreover, approximating the maximum d such that for any choice of failed edges there is a directed path of non-failed edges that starts from s and has length d turns out to be P-complete as well, for any given degree of relative accuracy of the approximation. Furthermore, given that every node υ will cause at least f(v) incoming edges to fail, the question whether there is a choice of failed edges such that s remains connected to t via non-failed edges turns out to be in NC, even for general graphs.