TY - GEN

T1 - The complexity of the reliable connectivity problem

AU - Kavadias, Dimitris

AU - Kirousis, Lefteris M.

AU - Spirakis, Paul

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.

PY - 1991

Y1 - 1991

N2 - Let G = (V;E) be a graph together with two distinguished nodes s and t, and suppose that to every node v εϵ V, a nonnegative integer f(v) ≤ degree(v) is assigned. Suppose, moreover, that each node v 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 with t with a path of non-failed edges for all possible choices of the failed edges. We first show that the complement of the Reliable Connectivity Problem is NP-complete and that this remains true even if G is restricted to the class of directed and acyclic graphs. However, we show that the problem is in P for directed and acyclic graphs if we assume that the edges caused to fail by each node i; are chosen only from the edges incoming to v. Concerning the parallel complexity of this 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. On the contrary, given that every node v will cause ai least f(v) incoming edges to fail, the question whether there is a choice of failed edges such that s remains connected with t via non-failed edges turns out to be in NC, even for general graphs.

AB - Let G = (V;E) be a graph together with two distinguished nodes s and t, and suppose that to every node v εϵ V, a nonnegative integer f(v) ≤ degree(v) is assigned. Suppose, moreover, that each node v 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 with t with a path of non-failed edges for all possible choices of the failed edges. We first show that the complement of the Reliable Connectivity Problem is NP-complete and that this remains true even if G is restricted to the class of directed and acyclic graphs. However, we show that the problem is in P for directed and acyclic graphs if we assume that the edges caused to fail by each node i; are chosen only from the edges incoming to v. Concerning the parallel complexity of this 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. On the contrary, given that every node v will cause ai least f(v) incoming edges to fail, the question whether there is a choice of failed edges such that s remains connected with t via non-failed edges turns out to be in NC, even for general graphs.

UR - http://www.scopus.com/inward/record.url?scp=85031912433&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031912433&partnerID=8YFLogxK

U2 - 10.1007/3-540-54345-7_69

DO - 10.1007/3-540-54345-7_69

M3 - Conference contribution

AN - SCOPUS:85031912433

SN - 9783540543459

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 259

EP - 260

BT - Mathematical Foundations of Computer Science 1991 - 16th International Symposium, Proceedings

A2 - Tarlecki, Andrzej

PB - Springer Verlag

T2 - 16th International Symposium on Mathematical Foundations of Computer Science, MFCS 1991

Y2 - 9 September 1991 through 13 September 1991

ER -