The Minimum Vulnerability Problem

Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Ashkan Norouzi-Fard, Sadra Yazdanbod, Hamid Zarrabi-Zadeh

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

We revisit the problem of finding k paths with a minimum number of shared edges between two vertices of a graph. An edge is called shared if it is used in more than one of the k paths. We provide a ⌊k/2⌋-approximation algorithm for this problem, improving the best previous approximation factor of k - 1. We also provide the first approximation algorithm for the problem with a sublinear approximation factor of O(n3/4), where n is the number of vertices in the input graph. For sparse graphs, such as bounded-degree and planar graphs, we show that the approximation factor of our algorithm can be improved to O(√n). While the problem is NP-hard, and even hard to approximate to within an O(log n) factor, we show that the problem is polynomially solvable when k is a constant. This settles an open problem posed by Omran et al. regarding the complexity of the problem for small values of k. We present most of our results in a more general form where each edge of the graph has a sharing cost and a sharing capacity, and there is a vulnerability parameter r that determines the number of times an edge can be used among different paths before it is counted as a shared/vulnerable edge.

Original languageEnglish (US)
Pages (from-to)718-731
Number of pages14
JournalAlgorithmica
Volume70
Issue number4
DOIs
StatePublished - Oct 25 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Approximation algorithms
  • Inapproximability
  • Network design
  • Shared edges

Fingerprint

Dive into the research topics of 'The Minimum Vulnerability Problem'. Together they form a unique fingerprint.

Cite this