Exact interdiction models and algorithms for disconnecting networks via node deletions

Siqian Shen, J. Cole Smith, Roshan Goli

Research output: Contribution to journalArticlepeer-review

84 Scopus citations


This paper analyzes the problem of maximizing the disconnectivity of undirected graphs by deleting a subset of their nodes. We consider three metrics that measure the connectivity of a graph: the number of connected components (which we attempt to maximize), the largest component size (which we attempt to minimize), and the minimum cost required to reconnect the graph after the nodes are deleted (which we attempt to maximize). We formulate each problem as a mixed-integer program, and then study valid inequalities for the first two connectivity objectives by examining intermediate dynamic programming solutions to k-hole subgraphs. We randomly generate a set of test instances, on which we demonstrate the computational efficacy of our approaches.

Original languageEnglish (US)
Pages (from-to)172-188
Number of pages17
JournalDiscrete Optimization
Issue number3
StatePublished - Aug 2012
Externally publishedYes


  • Mixed-integer programming
  • Network interdiction
  • Valid inequalities

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Exact interdiction models and algorithms for disconnecting networks via node deletions'. Together they form a unique fingerprint.

Cite this