The complexity of the reliable connectivity problem

Dimitris Kavadias, Lefteris M. Kirousis, Paul Spirakis

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)245-252
Number of pages8
JournalInformation Processing Letters
Issue number5
StatePublished - Sep 13 1991


  • Combinatorial problems
  • graph connectivity
  • P-completeness
  • parallel algorithms
  • reliability

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


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

Cite this