Detecting resilient structures in stochastic networks: A two-stage stochastic optimization approach

Maciej Rysz, Pavlo A. Krokhmal, Eduardo L. Pasiliao

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


We propose a two-stage stochastic programming framework for designing or identifying “resilient,” or “reparable” structures in graphs whose topology may undergo a stochastic transformation. The reparability of a subgraph satisfying a given property is defined in terms of a budget constraint, which allows for a prescribed number of vertices to be added to or removed from the subgraph so as to restore its structural properties after the observation of random changes to the graph's set of edges. A two-stage stochastic programming model is formulated and is shown to be (Formula presented.) -complete for a broad range of graph-theoretical properties that the resilient subgraph is required to satisfy. A general combinatorial branch-and-bound algorithm is developed, and its computational performance is illustrated on the example of a two-stage stochastic maximum clique problem.

Original languageEnglish (US)
Pages (from-to)189-204
Number of pages16
Issue number2
StatePublished - Mar 1 2017
Externally publishedYes


  • combinatorial branch-and-bound algorithm
  • maximum subgraph problem
  • resilience of subgraphs
  • stochastic graphs
  • stochastic maximum clique problem
  • two-stage stochastic optimization

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Detecting resilient structures in stochastic networks: A two-stage stochastic optimization approach'. Together they form a unique fingerprint.

Cite this