Structural Tractability Frontiers for Metric Repair

Abstract

Given a graph $G$ labeled with positive distances on each edge, what is the fewest number of edge distances that must be modified for $G$ to become a metric? It is known that this metric repair problem is $\mathrm{NP}$-hard on general graphs, with prior work focusing on approximations and fixed-parameter tractability with respect to properties of the input distance function. In this paper, we ask what structural properties of the graph itself make metric repair tractable. On the positive side, we give pseudo-polynomial time algorithms for series-parallel graphs, and by generalization, graphs of bounded treewidth. An immediate consequence of this result is a new algorithm for the length-bounded multicut problem, with a parameterized runtime bound in terms of the treewidth of a modestly augmented graph. Surprisingly, pseudo-polynomial time turns out to be the best one can hope for: We complement our algorithm with a proof that metric repair is weakly $\mathrm{NP}$-hard even on graphs of pathwidth at most six. We also prove that planarity does not help either, as the problem remains strongly $\mathrm{NP}$-hard even on grid graphs.