# The complexity of the reliable connectivity problem

Dimitris Kavadias, Lefteris M. Kirousis, Paul Spirakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

## Abstract

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.

Original language English (US) Mathematical Foundations of Computer Science 1991 - 16th International Symposium, Proceedings Andrzej Tarlecki Springer Verlag 259-260 2 9783540543459 https://doi.org/10.1007/3-540-54345-7_69 Published - 1991 16th International Symposium on Mathematical Foundations of Computer Science, MFCS 1991 - Kazimierz Dolny, PolandDuration: Sep 9 1991 → Sep 13 1991

### Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 520 LNCS 0302-9743 1611-3349

### Conference

Conference 16th International Symposium on Mathematical Foundations of Computer Science, MFCS 1991 Poland Kazimierz Dolny 9/9/91 → 9/13/91

## ASJC Scopus subject areas

• Theoretical Computer Science
• General Computer Science

## Fingerprint

Dive into the research topics of 'The complexity of the reliable connectivity problem'. Together they form a unique fingerprint.