Source-linked AI summary
A $5/2$-Approximation for Weighted Ultrametric Embedding with Outliers
Chenglin Fan
TL;DR
Weighted ultrametric embedding with outliers asks which points to delete so the retained metric is an ultrametric. The paper uses local configurations of violating triples to separate scales and reduce the residual problem to weighted Cluster Vertex Deletion. It gives a deterministic 5/2-approximation, improving the weighted factor-3 baseline, with O(n^5) arithmetic and comparison operations.
Problem
Weighted Ultrametric Embedding with Outliers asks for a minimum-weight set of points to delete so the remaining metric is an ultrametric.
Source: §1 · p. 1Method
The algorithm uses two local configurations of violating triples to isolate same-scale components and reduce the residual problem to weighted Cluster Vertex Deletion.
Source: §1.1 · p. 2, §1.2 · p. 2Results
The deterministic 5/2-approximation improves the weighted factor-3 baseline and uses O(n^5) arithmetic and comparison operations.
Source: §1.1 · pp. 1–2, §4.4 · p. 9Takeaways & Limitations
The result narrows the gap between the weighted factor-3 approximation and the UGC-based hardness below factor 2.
Source: §1 · p. 1Within a violation component, only the violating triples share a scale; pairwise distances need not all be equal, and different components may have different scales.
Source: §3.2 · p. 5
Abstract
from arXiv · showhide
Weighted ultrametric embedding with outliers asks for a minimum weight set of points whose deletion makes the remaining metric an ultrametric, equivalently, leaves no triple with a unique largest distance. We give a deterministic $5/2$-approximation using $O(n^5)$ arithmetic and comparison operations, improving the previous factor $3$ for arbitrary nonnegative vertex weights. Approximating the problem within any factor strictly below $2$ is UGC-hard.
1 Introduction
Weighted Ultrametric Embedding with Outliers seeks a minimum-weight deletion set that leaves an ultrametric. The paper improves the weighted factor-3 baseline to a deterministic 5/2-approximation by using local violation patterns to separate scales and reduce the residual problem to weighted Cluster Vertex Deletion.
1 Introduction
- The problem seeks a minimum-weight set of points to delete so the retained metric is an ultrametric, equivalently a maximum-weight subset that embeds isometrically.The input allows arbitrary nonnegative vertex weights.Source: §1 · p. 1
1.3 Related work
- The weighted factor-3 baseline extends the unweighted approximation of Sidiropoulos et al., while approximating within any factor below 2 is UGC-hard.Related work also studies editing distances or embedding with distortion; this paper instead deletes weighted points while preserving retained distances exactly.Source: §1 · p. 1, §1.3 · p. 2
1.1 Results
- A deterministic 5/2-approximation improves the weighted factor-3 baseline, using O(n^5) arithmetic and comparison operations.The implementation has polynomial bit complexity in the binary input length.Source: §1.1 · pp. 1–2
1.2 Approach
- Two local configurations of violating triples serve as deletion certificates; removing them leaves a core-free instance whose intersecting violations share a scale.The remaining components reduce to independent weighted Cluster Vertex Deletion instances, using Aprile et al.'s weighted 2-approximation as the terminal step.Source: §1.1 · p. 2, §1.2 · p. 2
2 Violations and local cost certificates
The section models ultrametric violations as triples to be hit by a deletion set, then identifies small core patterns that yield local cost certificates. These patterns also characterize when certain weighted certificates can exist on at most five vertices.
2.1 Notation and input model
- A three-point set is violating when one pairwise distance is strictly larger than the other two, and feasible deletion sets hit every violating triple.The input is a rational distance matrix with nonnegative rational vertex weights; isolated vertices of the violation hypergraph are not in any violating triple.Source: §2.1 · p. 3
2.2 The two cores
- The two non-induced cores are F4 = {abc, abd, acd} and F5 = {abc, abd, cde}; each has a cost-5 certificate forcing every feasible deletion set to pay at least 2.For F4 the common vertex has cost 2 and the other vertices cost 1; F5 uses unit costs. On at most five vertices, a core-free hypergraph has a 2-shadow that is three-colorable, so a color class has cost at most one third of total cost.Source: §2.2 · pp. 3–4
3 Scale separation and exact graph decomposition
The section uses threshold graphs to represent violations and analyzes how their scales interact in core-free instances. This structure yields independent graph-deletion problems for the violation components.
3.1 Threshold graphs
- At threshold r, an induced P3 is a violating triple, and a violation of scale exactly r induces an P3 in the threshold graph.Violations at smaller scales instead induce triangles.Source: §3.1 · p. 4, §3.3 · p. 6
3.2 Intersecting violations have the same scale
- Intersecting violations in a core-free instance have the same scale, so every nontrivial violation component has one common violation scale.This does not imply that all pairwise distances within a component are equal, or that different components share a scale.Source: §3.2 · p. 5
3.3 Feasibility-preserving reduction to CVD
- In a core-free instance, the metric remains ultrametric after deletion exactly when each component’s threshold graph becomes a cluster graph.The decomposition also makes the optimum deletion weight equal to the sum of the component CVD optima.Source: §3.3 · p. 6
- A weighted CVD 2-approximation gives a 2-approximation for the ultrametric deletion problem on core-free instances.The method applies ClusterDelete separately to the component graphs and retains isolated vertices of the violation hypergraph.Source: §3.3 · p. 6
4 Algorithm and approximation analysis
Algorithm 1 combines a single enumeration of local cores with a terminal decomposition into weighted CVD instances; the analysis proves feasibility, a 5/2 weight bound, and O(n^5) arithmetic and comparison time.
4.1 A single pass over candidate cores
- A single fixed-order pass over template labelings uses only active candidates whose three specified triples are violating, and each reduction removes at least one active point.The enumeration can be streamed, and distance tests use the original matrix.Source: §4.1 · p. 7
4.2 Feasibility and progress
- The returned deletion set is feasible because the residual instance is core-free and its threshold-graph components reduce to cluster-deletion instances.Each resulting graph minus its CVD solution is a cluster graph, yielding an ultrametric remainder.Source: §4.2 · p. 8
4.3 Charging the original weights
- Theorem 4.4 states that the set A returned by Algorithm 1 satisfies w(A) ≤ (5/2) OPTU(X, w).Source: §4.3 · p. 9
- The residual core-free instance receives a factor-2 approximation, while the local core reductions account for the increase to 5/2.Every feasible deletion set hits all three violating triples of each used core, supporting the charging lower bound.Source: §4.3 · pp. 8–9
4.4 Running time and exact arithmetic
- The O(n^5) running time is dominated by enumerating injective labelings of the four- and five-vertex templates.Exact rational comparisons and polynomial-bit-length residual weights preserve polynomial bit complexity.Source: §4.4 · p. 9
A Classification of weighted small-core certificates
For 3-uniform hypergraphs on at most five vertices, the absence of the two core patterns forces a three-colorable 2-shadow and rules out a nonzero weighted 5/2 certificate.
Appendix A
- Without F4 or F5, the 2-shadow is K4-free, as every possible K4 configuration would force one of the two core patterns.The proof checks the cases according to how many hyperedges lie entirely within the four vertices.Source: A Classification of weighted… · p. 11
- Every K4-free graph on at most five vertices has a proper three-coloring, and each color class meets every hyperedge.A hyperedge forms a triangle in the 2-shadow and therefore uses all three colors.Source: A Classification of weighted… · p. 11
- If a core is present, a cost vector of total weight 5 makes every transversal of its three displayed edges cost at least 2.The vector assigns cost 2 to the common vertex and 1 to three others for Type I, and unit costs for Type II.Source: A Classification of weighted… · p. 11
- Consequently, no nonzero weighted 5/2 certificate exists for a core-free hypergraph on at most five vertices.The color classes are transversals, with one class costing at most c(W)/3.Source: A Classification of weighted… · p. 11