AI summaryⓘ
The authors study a problem called Ultrametric Violation Distance, where the goal is to change the fewest distances between points so that they fit a special kind of metric called an ultrametric. Previous work focused on error measured in other ways, but this paper looks deeper into the version using the count of changed distances (the 9-norm). Building on recent algorithms that approximate solutions, the authors explore how the problem can be simplified (kernelization) and solved efficiently when the number of changes needed is small (fixed-parameter tractability). They show the problem can be reduced to a smaller instance with about k squared points and give a fast algorithm with running time proportional to 9 to the power of k times a polynomial in n, which they prove is essentially the best possible.
UltrametricViolation DistanceL0-normKernelizationFixed-Parameter TractabilityApproximation AlgorithmComplexityParameterized AlgorithmComputational GeometryMetric Spaces
Abstract
In the Ultrametric Violation Distance problem, we are given a set of distances between $n$ points, and the goal is to modify the minimum number of distances so that the resulting set forms a valid ultrametric. In other words, the task is to fit an ultrametric to the given data, where the quality of the fit is measured by the $\ell_0$-norm of the error. While variants of this problem under the $\ell_\infty$ and $\ell_1$-norms have been well studied, the complexity of Ultrametric Violation Distance under the $\ell_0$-norm remained largely unexplored until recently. This changed with the work of Cohen-Addad, Fan, Lee, and Mesmay [FOCS 2022], who introduced a constant-factor approximation algorithm. Significant further progress on approximation algorithms was made in subsequent work by Charikar and Gao [SODA 2024], and by An, Kao, Lee, and Lee [FOCS 2025]. In this paper, we initiate a systematic study of Ultrametric Violation Distance from the perspectives of kernelization and fixed-parameter tractability (FPT). By the work of Fan, Gilbert, Raichel, Sonthalia, and Van Buskirk [SWAT 2020], the problem is known to be FPT when parameterized by the number of violated distances $k$. We show that the problem admits a kernel with $\mathcal{O}(k^2)$ points. Additionally, we present a single-exponential-time algorithm with running time $9^k \cdot n^{\mathcal{O}(1)}$, which is asymptotically tight.