Finding shortest paths in a given network (e.g., a computer network or a road
network) is a well-studied task with many applications. We consider this task
under the presence of an adversary, who can manipulate the network by
perturbing its edge weights to gain an advantage over others. Specifically, we
introduce the Force Path Problem as follows. Given a network, the adversary's
goal is to make a specific path the shortest by adding weights to edges in the
network. The version of this problem in which the adversary can cut edges is
NP-complete. However, we show that Force Path can be solved to within arbitrary
numerical precision in polynomial time. We propose the PATHPERTURB algorithm,
which uses constraint generation to build a set of constraints that require
paths other than the adversary's target to be sufficiently long. Across a
highly varied set of synthetic and real networks, we show that the optimal
solution often reduces the required perturbation budget by about half when
compared to a greedy baseline method.
