Metraipolis › archive › dc_ccb79c354501
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics — arXiv:2610.07690
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.07690
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T13:40:32.678Z
- SHA-256 of the archived text
8dc2d7223c652b2defb7be9d7940955ac9a6e7ecb449ed0848e904eb898d8e90- Stable URL of this page
https://metraipolis.com/documento/dc_ccb79c354501
How to cite
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics — arXiv:2610.07690 — arXiv (en), https://arxiv.org/abs/2610.07690 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ccb79c354501 (Metraipolis archive dc_ccb79c354501, sha256 8dc2d7223c652b2defb7be9d7940955ac9a6e7ecb449ed0848e904eb898d8e90)
BibTeX
@misc{dcccb79c354501,
title = {How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics — arXiv:2610.07690},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.07690},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ccb79c354501; sha256 8dc2d7223c652b2defb7be9d7940955ac9a6e7ecb449ed0848e904eb898d8e90},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07690. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most $k$ weights can be changed to form a metric. Motivated by metric repair for noisy data, the problem admits a polynomial-time $O(\log n)$-approximation due to Cohen-Addad, Fan, Lee and de Mesmay [SIAM J. Comput., 2025]. In the context of parameterized complexity, Fan, Gilbert, Raichel, Sonthalia and Van Buskirk [SWAT 2020] gave a $k^{O(k)}n^{O(1)}$-time algorithm. Fomin, Golovach and More [IPEC 2026] obtained an $O(k^2)$ kernel and a single-exponential algorithm for the ultrametric case. They asked whether general metrics admit a single-exponential algorithm and a polynomial kernel, and whether the tree-metric analogue is fixed-parameter tractable. We answer all three questions. We give a $2^{O(k)}n^{O(1)}$-time algorithm and prove that, unless ETH fails, no $2^{o(k)}n^{O(1)}$-time algorithm exists, even when all input distances lie in $\{1,2,3\}$. We also give a kernel with at most $6k$ vertices. The kernel supports solution lifting and can precede any approximation algorithm. Combined with the $O(\log n)$-approximation of Cohen-Addad, Fan, Lee and de Mesmay, it yields an $O(\log \mathrm{OPT})$-approximation at no asymptotic cost in running time. Both results extend to an interval generalization in which each edge $e$ has an observed value $M_e$ and an admissible range $[A_e,B_e]$ within which it may be reassigned; the kernel then has $7k$ vertices. Finally, Tree Metric Violation Distance is fixed-parameter tractable and solvable in $k^{O(k)}n^{O(1)}$ time.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.07690 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T13:13:03.916Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).