The complexity of the reliable connectivity problem

Dimitris Kavadias, Lefteris M. Kirousis, Paul Spirakis

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


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 languageEnglish (US)
Title of host publicationMathematical Foundations of Computer Science 1991 - 16th International Symposium, Proceedings
EditorsAndrzej Tarlecki
PublisherSpringer Verlag
Number of pages2
ISBN (Print)9783540543459
StatePublished - 1991
Event16th International Symposium on Mathematical Foundations of Computer Science, MFCS 1991 - Kazimierz Dolny, Poland
Duration: Sep 9 1991Sep 13 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume520 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Symposium on Mathematical Foundations of Computer Science, MFCS 1991
CityKazimierz Dolny

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this