Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems

We consider the

k

most vital edges (nodes) and min edge (node) blocker versions of the 1-median and 1-center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the

k

most vital edges (nodes) 1-median (respectively 1-center) problem consists of finding a subset of

k

edges (nodes) whose removal from the graph leads to an optimal solution for the 1-median (respectively 1-center) problem with the largest total weighted distance (respectively maximum weighted distance). The complementary problem, min edge (node) blocker 1-median (respectively 1-center), consists of removing a subset of edges (nodes) of minimum cardinality such that an optimal solution for the 1-median (respectively 1-center) problem has a total weighted distance (respectively a maximum weighted distance) at least as large as a specified threshold. We show that

k

most vital edges 1-median and

k

most vital edges 1-center are

NP

-hard to approximate within a factor

$\frac{7}{5}-\epsilon$

and

$\frac{4}{3}-\epsilon$

respectively, for any

ε

> 0, while

k

most vital nodes 1-median and

k

most vital nodes 1-center are

NP

-hard to approximate within a factor

$\frac{3}{2}-\epsilon$

, for any

ε

> 0. We also show that the complementary versions of these four problems are

NP

-hard to approximate within a factor 1.36.