Jul 2026
Structural Tractability Frontiers for Metric Repair
This paper asks what structural properties of the graph itself make metric repair tractable, and gives pseudo-polynomial time algorithms for series-parallel graphs, and by generalization, graphs of bounded treewidth and a new algorithm for the length-bounded multicut problem.
Asaf Etgar, A. Gilbert, Jamie Tucker-Foltz
· arXiv.org · 0 citations