Abstract
Metric spaces are fundamental to many data analysis tasks, including clustering and dimensionality reduction. However, real-world data often contains noise that violates the triangle inequality. This paper investigates the Generalized Metric Repair problem, where the goal is to modify the minimum number of edge weights in a general graph to satisfy a metric. We establish that the problem is APX-hard via a reduction from MULTICUT and provide several approximation algorithms. Furthermore, we show that the problem is fixed-parameter tractable (FPT) for the class of $\varsigma$-chordal graphs.
Introduction
In a metric space, the distance between any two points $u$ and $v$ must satisfy the triangle inequality: $d(u, v) \leq d(u, w) + d(w, v)$ for any intermediate point $w$. When data is collected from noisy sensors or incomplete observations, these constraints are frequently violated. Previous work on "Sparse Metric Repair" focused on complete graphs, where every pair of points has a defined distance. This paper generalizes the problem to arbitrary weighted graphs $G = (V, E, w)$, allowing for more flexible modeling of sparse datasets where only specific relationships are known.
Structural Characterization: Broken Cycles
The core of the metric repair problem lies in identifying and fixing "broken cycles." A cycle is considered broken if it contains an edge (the "heavy" edge) whose weight exceeds the sum of the weights of all other edges in the cycle. The difference between the heavy edge's weight and the path sum is called the deficit. A graph satisfies a metric if and only if it contains no broken cycles.
To determine if a proposed set of edge modifications $S$ successfully repairs the graph, the authors utilize a verification procedure.
As shown in the VERIFIER algorithm, a set $S$ is valid if, after setting the weights of edges in $S$ to a sufficiently large value $M$ and recomputing shortest paths, only the weights of edges originally in $S$ are altered. This structural insight allows the problem to be framed as a covering problem over the set of broken cycles.
Hardness and the MULTICUT Connection
A key contribution of this work is establishing the computational complexity of generalized metric repair. The authors provide an approximation-preserving reduction from the MULTICUT problem. This reduction implies that metric repair is APX-hard. Furthermore, under the Unique Games Conjecture, the problem cannot be approximated within any constant factor, highlighting a significant jump in difficulty from the complete graph case.
Algorithmic Results
Despite the hardness results, the paper presents several positive algorithmic outcomes:
- $(L+1)$-Approximation: By viewing the problem as a hitting set problem on broken cycles, the authors achieve an approximation ratio tied to $L$, the maximum number of edges in any broken cycle.
- $O(\kappa \log n)$-Approximation: The authors introduce an algorithm whose performance depends on $\kappa$, the number of distinct deficit values in the graph. This is particularly useful when the noise follows specific patterns.
- Complexity Improvements for Complete Graphs: For the specific case of complete graphs ($K_n$), the authors improved the runtime analysis of existing algorithms from $O(n^6)$ to $O(n^5)$.
- FPT for $\varsigma$-chordal Graphs: For graphs where the largest chordless cycle has a bounded size $\varsigma$, the problem is shown to be fixed-parameter tractable when parameterized by the size of the optimal solution ($OPT$). This provides an efficient solution for a broad and practically relevant class of graphs.
Conclusion
By generalizing metric repair to arbitrary graphs, this work bridges the gap between theoretical metric properties and practical, sparse data analysis. The connection to MULTICUT provides a deep understanding of the problem's complexity, while the new approximation and FPT algorithms offer viable paths for handling metric violations in structured datasets. Future research may explore whether the dependence on the deficit count $\kappa$ can be further reduced or if it represents a fundamental limit of the problem.
Summary updated