The Minimum Vulnerability Problem
Authors:
Sepehr Assadi, Ehsan Emamjomeh-Zadeh,
Ashkan Norouzi-Fard, Sadra Yazdanbod,
Hamid Zarrabi-Zadeh
Journal:
Algorithmica, 70(4), 2014.
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 available for the problem. We also
provide the first approximation algorithm for the problem with a sublinear
approximation factor of O(n^{3/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(\sqrt{n}). While the problem is NP-hard, and even hard to
approximate to within a 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 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.
Journal version:
[PDF]
BibTex:
[DBLP]