  Many modern data analysis algorithms either assume that or are considerably
more efficient if the distances between the data points satisfy a metric. These
algorithms include metric learning, clustering, and dimensionality reduction.
Because real data sets are noisy, the similarity measures often fail to satisfy
a metric. For this reason, Gilbert and Jain [11] and Fan, et al. [8] introduce
the closely related problems of $\textit{sparse metric repair}$ and
$\textit{metric violation distance}$. The goal of each problem is to repair as
few distances as possible to ensure that the distances between the data points
satisfy a metric. We generalize these problems so as to no longer require all
the distances between the data points. That is, we consider a weighted graph
$G$ with corrupted weights w and our goal is to find the smallest number of
modifications to the weights so that the resulting weighted graph distances
satisfy a metric. This problem is a natural generalization of the sparse metric
repair problem and is more flexible as it takes into account different
relationships amongst the input data points. As in previous work, we
distinguish amongst the types of repairs permitted (decrease, increase, and
general repairs). We focus on the increase and general versions and establish
hardness results and show the inherent combinatorial structure of the problem.
We then show that if we restrict to the case when $G$ is a chordal graph, then
the problem is fixed parameter tractable. We also present several classes of
approximation algorithms. These include and improve upon previous metric repair
algorithms for the special case when $G = K_n$
