Abstract
We revisit the problem of finding
$$k$$
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$$
k
paths. We provide a
$${\lfloor {k/2}\rfloor }$$
⌊
k
/
2
⌋
-approximation algorithm for this problem, improving the best previous approximation factor of
$$k-1$$
k
-
1
. We also provide the first approximation algorithm for the problem with a sublinear approximation factor of
$$O(n^{3/4})$$
O
(
n
3
/
4
)
, where
$$n$$
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})$$
O
(
n
)
. While the problem is NP-hard, and even hard to approximate to within an
$$O(\log n)$$
O
(
log
n
)
factor, we show that the problem is polynomially solvable when
$$k$$
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$$
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$$
r
that determines the number of times an edge can be used among different paths before it is counted as a shared/vulnerable edge.