Structural Tractability Frontiers for Metric Repair
2026-07-31 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to fix a graph's edge distances so they follow the rules of a metric (like distances in real life). They show that this fixing problem is very hard in general, but they found more efficient algorithms for special graph types called series-parallel and bounded treewidth graphs. They also prove that even with these constraints, the problem remains hard in some cases and isn't easier on planar or grid graphs. Their findings highlight exactly when the problem is manageable and when it isn't based on graph structure.
metric repairgraphedge distancesseries-parallel graphstreewidthpathwidthpseudo-polynomial timeNP-hardplanaritylength-bounded multicut
Authors
Asaf Etgar, Anna C. Gilbert, Jamie Tucker-Foltz
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.