Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Let G = (V, E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s1 and s2 to, respectively, a given vertex t1, and each vertex of a given subset of vertices T2.

Original languageEnglish (US)
Pages (from-to)137-149
Number of pages13
JournalDiscrete Applied Mathematics
Issue number2
StatePublished - Jan 15 2007

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


  • Disjunction and conjunctions of paths and cuts
  • Path and cut enumeration
  • Reliability theory


Dive into the research topics of 'Enumerating disjunctions and conjunctions of paths and cuts in reliability theory'. Together they form a unique fingerprint.

Cite this