Ultrametric Violation Distance: Polynomial Kernel and FPT Algorithm

Fedor V. Fomin; Petr A. Golovach; Yash Hiren More

REVIEW 3 major objections 5 minor 25 references

Ultrametric Violation Distance: Polynomial Kernel and FPT Algorithm

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Ultrametric fitting with few changed distances admits a kernel of O(k^2) points and a single-exponential 9^k algorithm.

desk verdict Real advance: first polynomial kernel and single-exponential FPT for ℓ0 Ultrametric Violation Distance, but the 9^k running-time proof rests on an under-formalized monotonicity invariant. read the letter →

arxiv 2608.09546 v1 pith:P3GK3VYE submitted 2026-08-10 cs.DS

Fedor V. Fomin , Petr A. Golovach , Yash Hiren More This is my paper · ORCID

classification cs.DS

keywords UltrametricViolationDistanceKernelizationFixed-ParameterTractabilityClusterEditingHierarchicalClusteringℓ0-normDivisiveBranching

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the problem of fitting an ultrametric to a given distance table by changing as few entries as possible—the ℓ0-norm Ultrametric Violation Distance—is fixed-parameter tractable in a much stronger sense than the prior $k^{{O(k)}}$ bound. Working with a constrained version that also enforces per-pair lower and upper thresholds, it shows every yes-instance can be reduced in polynomial time to an equivalent one on O($k^{2}$) points, yielding a kernel of size O($k^{4}$ log k). It then gives a single-exponential algorithm running in O(9^k·k·|X|^2), which is asymptotically tight because the special case Cluster Editing admits no $2^{{o(k)}}$ algorithm unless the Exponential Time Hypothesis fails. The two results rest on quite different machinery: threshold-aware 'bad triangles' for the kernel, and a level-by-level divisive branching scheme for the algorithm.

What carries the argument

The kernelization is carried by the classification of each edge as fixed, unfit, or normal, and by the notion of a bad triangle with respect to an edge $xy$: a triple that violates the ultrametric inequality, or whose non-$xy$ edges are both unfit, or where $xy$ is unfit and the other two edges are unequal or exceed a threshold. A sequence of reduction rules tightens thresholds and fixes edges until every edge is in only $O(k)$ bad triangles; at that point a vertex incident to no unfit edge and contained in no bad triangle can be deleted safely, and a counting argument bounds the remaining points by $3k^2+2k$. The FPT algorithm proceeds from the largest distance level to the smallest, using the fact that in any ultrametric the pairs below a level form a disjoint union of cliques. To keep the branching single-exponential despite the fact that lowering an edge's value is not necessarily final, the algorithm marks edges whose eventual value is undecided and uses a measure $\mu$ that consumes $2$ units for an increase, $1$ for marking, and $1$ for finalizing a marked edge, so every edited edge costs at most $2$ units and the search tree has at most $3^{2k}=9^k$ leaves.

What would settle it

Brute-force search over all distance matrices on five points with integer distances from a small set (say $\{1,2,3,4\}$) and $k=2$: compare the algorithm's decisions against the true optimum found by enumerating all ultrametrics within edit distance $2$. If any yes-instance is rejected, or any optimal editing path must increase an edge that was previously decreased at a higher level, Claim 24 and the measure argument behind Theorem 2 would be falsified.

Watch

Extended reading notes

Core claim

The central claim is that the Constrained Ultrametric Violation Distance problem (CUVD) is solvable with a polynomial kernel and a single-exponential FPT algorithm. Theorem 1 states that any instance can be transformed in polynomial time into an equivalent instance with at most $3k^2+2k$ points, encoding in $O(k^4\log k)$ bits. Theorem 2 states that CUVD can be solved in $O(9^k \cdot k \cdot |X|^2)$ time. Because the unconstrained Ultrametric Violation Distance is the special case with thresholds $0$ and $\max D$, both results apply directly to the ℓ0-norm fitting problem. The authors also observe that the exponential base cannot be improved to subexponential, since Cluster Editing—the case of two distance values—would then also have a $2^{o(k)}$ algorithm, contradicting the Exponential Time Hypothesis.

Load-bearing premise

The $9^k$ running time relies on Claim 24, which asserts that at a given distance level an optimal solution only decreases edges currently at that level's value and never increases them, so each edited edge consumes at most two units of the branching measure; if a valid solution could both increase and decrease the same edge, the measure would not cover the budget and the $3^{2k}$ leaf bound would fail.

Editorial extensions

If this is right

The ℓ0-norm Ultrametric Violation Distance problem is FPT with running time $O(9^k \cdot k \cdot |X|^2)$, improving the previous $k^{O(k)}$ bound from the metric-repair reduction.
Any yes-instance can be preprocessed to an equivalent instance on $O(k^2)$ points in polynomial time, so the combinatorial explosion can be confined to the parameter $k$ alone.
No subexponential algorithm $2^{o(k)}\cdot n^{O(1)}$ can exist unless ETH fails, because Cluster Editing is the two-distance special case.
The constrained problem CUVD with per-pair lower and upper thresholds costs no more than the unconstrained version, so algorithms for it apply directly to fitting problems that must respect interval constraints.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the kernel's reduction rules run in polynomial time and shrink the point set, they could serve as a practical preprocessing heuristic for hierarchical clustering with noisy distances, even when the parameter k is not tiny.
The bound $3k^2+2k$ comes from charging each edited edge with $O(k)$ bad triangles; a tighter charging scheme that separates isosceles from scalene cases might yield an $O(k)$-point kernel, matching the Cluster Editing bound.
The same divisive 'levels as cluster graphs' view may extend to Tree Metric Violation Distance, whose parameterized complexity is open, if an analogue of Claim 24 can be proved for tree metrics.
A small modification of the measure—charging 1 instead of 2 for an increase that never touches the edge again—might lower the base below 9, though the current analysis does not support that.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline is simple: this is the first polynomial kernel and the first single-exponential FPT algorithm for ℓ0-norm Ultrametric Violation Distance, and the result is genuinely new. The k^{O(k)} FPT bound from Fan et al. is improved to 9^k, and the O(k^2)-point kernel closes a question that Cohen-Addad et al. effectively left open. The paper also introduces the threshold-constrained variant CUVD, which is a natural and useful generalization, and Proposition 5—reusing the Farach–Kannan–Warnow sandwich algorithm—gives a clean polynomial-time check for a guessed edit set.

The kernelization is the strongest part. The bad-triangle classification (types i–iii) is carefully designed, the reduction rules are individually plausible, and the order-preserving scaling argument is tidy. I read the irrelevant-vertex removal proof closely and it holds up; the layering argument is sound. No load-bearing flaw there.

The soft spots are concentrated in the FPT part. The stress-test note is right: the 9^k bound depends on Claim 24, which says that at level i an edge in D_i can only be decreased, never increased. The proof is a two-sentence induction that does not state or prove the branch-consistency invariant. The branching cases silently rely on the fact that in a branch consistent with some valid solution, no solution would require increasing a D_i edge at level i. That invariant is plausible—increasing such an edge does not change its non-edge status in G_i, so it cannot fix a violated triangle at that level—but it is not written down. As the paper stands, the measure argument is not fully formalized and the 3^{2k} leaf bound is not yet established. I think this is fixable, but it needs real work, not copy-editing.

Two smaller issues. Claim 19's note that type-(ii) bad-triangle vertices are "already taken into account" by the type-(iii) bound is under-justified; those vertices are incident to unfit edges, but not necessarily part of a type-(iii) triangle with an unfit base edge. The O(k^2) kernel survives even if you add a separate 2k term, but the stated 3k^2+2k count may need a small correction. And the abstract's "asymptotically tight" overreaches: ETH gives no subexponential, but it says nothing about whether 9 is the right base, and "linear for constant k" is a weak sense of tight.

Who is this for? Researchers in parameterized algorithms and anyone working on metric/ultrametric violation distances. The kernel is the headline contribution; the FPT algorithm is a promising framework that needs a more careful analysis. I would send this to a serious referee and require the FPT proof to be tightened before acceptance. The paper is worth engaging with.

Referee Report

3 major / 5 minor

Summary. The paper introduces Constrained Ultrametric Violation Distance (CUVD), a generalization of the ℓ0-norm Ultrametric Violation Distance in which every pair also has lower and upper thresholds. The main results are Theorem 1, a kernel with 3k^2+2k points and total size O(k^4 log k), and Theorem 2, an FPT algorithm with running time O(9^k·k·|X|^2). The kernelization is built from a sequence of reduction rules that tighten thresholds, fix edges, and delete 'irrelevant' vertices, followed by an order-preserving scaling of all distance values. The FPT algorithm processes distance levels from largest to smallest, maintains an auxiliary graph at each level, and branches on violated triangles; a measure µ=2k−|U| is used to bound the number of leaves by 3^{2k}=9^k.

Significance. If the proofs are completed, the results would answer two natural open questions for a problem that was previously known to be FPT only with k^{O(k)} running time: polynomial kernelization and single-exponential FPT. The kernelization is technically interesting because CUVD is not a simple d-Hitting Set problem; the threshold-tightening rules and the irrelevant-vertex lemma are nontrivial. The FPT algorithm is also conceptually attractive, with a measure that charges at most two units per edited edge. The ETH-based lower bound quoted from Cluster Editing makes a single-exponential base 9^k a meaningful target. However, the proof of the central monotonicity claim (Claim 24) and the linear-time cluster-update claim in the running-time analysis are not yet established, so the FPT part currently needs substantial revision.

major comments (3)

[4, Claim 24] The proof of Claim 24 is not sufficient for the role it plays. The statement that at a given level i one can only decrease the weights of edges in D_i is used to make the Branching Cases Subroutine exhaustive and to justify the measure charge of at most two units per edited edge, but the proof is a short induction that never formalizes the invariant relating the current branch to a valid solution. In particular, it does not explain why, in a branch consistent with some solution, an edge currently in D_i cannot need to be increased at level i. Without that invariant, the three branch cases may omit valid solutions, and the leaf bound 3^{2k} does not follow. Please state and prove the branch-consistency invariant, or modify the branching to include the missing cases, before the running time can be accepted.
[4, Running Time Analysis] The claim that one can check in O(|D_{i-1}|) time whether the graph obtained from a cluster graph by deleting the D_{i-1} edges is again a cluster graph is asserted without proof or reference. This is load-bearing because the algorithm has L=O(|X|^2) non-branching steps per path; an O(|X|^2) check at each step would give O(|X|^4) per path, contradicting the stated O(9^k·k·|X|^2) bound. Please supply the linear-time procedure or revise the running time.
[3, Claim 19] The counting argument for type (ii) bad triangles is under-explained. The text says that the vertices of such triangles are 'already taken into account' by the bound for type (iii) triangles, but a vertex can be incident to an unfit edge without belonging to any type (iii) bad triangle, so the formula as written does not obviously cover it. The step can be repaired by making explicit that the '+2' term in |U|·(3k+2) counts the two endpoints of each unfit edge, so every vertex incident to a U edge is covered; please rewrite this portion of Claim 19 accordingly.

minor comments (5)

[3, Reduction Rule 5] The phrase 'Because of Reduction Rule 2, there is i such that xz_i, yz_i ∈ N∪F' is confusing; by Definition 8 the two non-reference edges of a bad scalene triangle are already in N∪F for every i. The intended argument appears to be that at least one of the k+1 triangles has xy not already equal to M; please clarify.
[3, Claim 20] In the proof of Claim 20, the sentence 'x = y if and only if f(x) = f(y)' uses x and y as distance values; the notation should be changed to avoid confusion with the points of X.
[4, Algorithm 1] The pseudocode does not explicitly maintain the auxiliary graphs G_i, although the surrounding text says that the algorithm creates G_L and updates it as edge weights change; adding an explicit update rule for G_i would improve readability and verifiability.
[1.2 and Figure 2] The caption of Figure 2 refers to 'violated triples' abd, acd, bcd but does not give the numeric distances used in the figure; please add the distances or a precise description so the example is self-contained.
[3, end of Theorem 1 proof] The sentence 'Because the total number of triangles is (|X| choose 3), we have that the reduction rules can be executed in polynomial time' is not by itself sufficient; please state a bound on the number of times the threshold-tightening rules can be applied before a vertex is deleted or the parameter decreases.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: kernel and FPT derivations are self-contained; Claim 24 is a proof-gap concern, not an input-output collapse.

full rationale

The central derivation chain is not circular. The previously known FPT result is cited to Fan et al. [37] via the tropicalization reduction in [29, Corollary 5.16], but it is only used as background; Theorem 1 and Theorem 2 are proved independently. Proposition 5 is either derived from the external Farach-Kannan-Warnow sandwich algorithm [40] or proved from scratch in Appendix A; it is a polynomial-time checking oracle, not a fitted parameter or a disguised form of the kernel bound. Claims 10-19 are direct soundness proofs for the reduction rules: the O(k^2) point bound in Claim 19 counts bad triangles after the rules have been exhaustively applied, and Reduction Rule 9 converts that counting into a no-instance conclusion. The kernel size is thus derived rather than assumed. Claim 20's order-preserving scaling is justified by strict monotonicity and by Corollary 6 bounding solution values; it does not smuggle the target equivalence into the construction. In Section 4, every branching case reduces the measure mu by at least 1, and the leaf bound 3^mu <= 9^k is a direct measure argument. The only fragile passage is Claim 24: its two-sentence induction asserts that at a given level an edge in D_i can only be decreased, and the paper does not fully formalize the branch-consistency invariant that would rule out a later contradictory increase. This is a genuine rigor gap, but it is not circular: Claim 24 is not defined in terms of the 9^k running time, and the measure bound is not used as an input to the claim. The self-citations [43] and [44] are standard ETH lower bounds and methodology references, not self-supporting uniqueness or ansatz justifications. No fitted parameter is renamed as a prediction, and no equation reduces to its own input by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central results rest on standard background in parameterized complexity and ultrametric theory plus two external algorithmic results (sandwich algorithm and tropicalization reduction). No free parameters are fitted to data and no new physical or mathematical entities are postulated. The CUVD problem variant is a definitional generalization, not an independent evidence-bearing entity.

assumptions (4)

domain assumption Exponential Time Hypothesis: Cluster Editing admits no 2^{o(k)} n^{O(1)} algorithm unless ETH fails.
Used to argue that the exponential dependence on k in CUVD cannot be subexponential, by reduction from Cluster Editing; cited to [43,54].
domain assumption Ultrametric Violation Distance reduces to Metric Violation Distance by tropicalization d ↦ n·d (Cohen-Addad et al., Corollary 5.16).
Used only to establish the previous k^{O(k)} FPT bound for background, not as a load-bearing step for the new theorems.
domain assumption The Farach-Kannan-Warnow algorithm for the Ultrametric Graph Sandwich problem runs in polynomial time (Proposition 5 is derived from [40, Theorem 4]).
Proposition 5, which lets the FPT algorithm test a guessed set of edited edges, relies on this external polynomial-time sandwich result.
standard math A graph whose edges are pairs at distance below a threshold in an ultrametric is a disjoint union of cliques.
This cluster-graph characterization of ultrametric levels is used throughout the FPT algorithm, e.g., in Lemma 23 and the level-by-level branching.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Ultrametric Violation Distance: Polynomial Kernel and FPT Algorithm." pith.science (2026). https://pith.science/paper/P3GK3VYE

@misc{pith2026260809546,
  author       = {Pith},
  title        = {Pith review of: Ultrametric Violation Distance: Polynomial Kernel and FPT Algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P3GK3VYE}},
  note         = {Machine review of arXiv:2608.09546}
}

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 12 canonical work pages

[1]

On the approximability of numerical taxonomy (fitting distances by tree metrics).SIAM Journal on Computing, 28(3):1073–1085, 1999.doi:10.1137/S0097539796309764

1 Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, and Mikkel Thorup. On the approximability of numerical taxonomy (fitting distances by tree metrics).SIAM Journal on Computing, 28(3):1073–1085, 1999.doi:10.1137/S0097539796309764. 2 Nir Ailon and Moses Charikar. Fitting tree metrics: Hierarchical clustering and phylogeny. SIAM Journal on Comput...

doi:10.1137/s0097539796309764 1999
[5]

A $(1+\epsilon)$-Approximation for Ultrametric Embedding in Subquadratic Time

URL:https://arxiv.org/abs/2503.13409,arXiv:2503.13409. 9 Amir Ben-Dor, Ron Shamir, and Zohar Yakhini. Clustering gene expression patterns.Journal of Computational Biology, 6(3/4):281–297,

work page Pith review arXiv
[6]

A golden ratio parameterized algorithm for cluster editing.Journal of Discrete Algorithms, 16:224–233, 2012.doi:10.1016/j.jda.2012.04.001

11 Sebastian Böcker. A golden ratio parameterized algorithm for cluster editing.Journal of Discrete Algorithms, 16:224–233, 2012.doi:10.1016/j.jda.2012.04.001. 12 Sebastian Böcker and Peter Damaschke. Even faster parameterized cluster deletion and cluster editing.Inf. Process. Lett., 111(14):717–721,

work page doi:10.1016/j.jda.2012.04.001 2012
[8]

16 Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl

Association for Computing Machinery.doi:10.1145/3717823.3718181. 16 Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl. Understanding the cluster linear program for correlation clustering. InProceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1605–1616. ACM,

arXiv
[12]

Clustering with qualitative information

23 Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. InProceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), pages 524–533. IEEE Computer Society,

work page 2003
[14]

A2k kernel for the cluster editing problem.Journal of Computer and System Sciences, 78(1):211 – 220, 2012.doi:10.1016/j.jcss.2011.04.001

26 Jianer Chen and Jie Meng. A2k kernel for the cluster editing problem.Journal of Computer and System Sciences, 78(1):211 – 220, 2012.doi:10.1016/j.jcss.2011.04.001. 27 Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, and Mikkel Thorup. Fitting distances by tree metrics minimizing the total error within a constant factor. J. ACM...

work page doi:10.1016/j.jcss.2011.04.001 2012
[15]

30 Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman

URL: https://doi.org/10.1137/22m1520190,doi:10.1137/22M1520190. 30 Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman. Handling correlated rounding error via preclustering: A 1.73-approximation for correlation clustering. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1082–1104, 2023.doi:10.1109/FOCS57990.202...

arXiv
[17]

Tree violation distance under constraints

35 Debarati Das, Evangelos Kipouridis, and Joachim Spoerhase. Tree violation distance under constraints. InProceedings of the 2026 SIAM Symposium on Simplicity in Algorithms (SOSA), pages 355–364, 2026.doi:10.1137/1.9781611978964.28. F.V. Fomin, P.A. Golovach, and Y. More 29 36 Patrik D’haeseleer. How does gene expression clustering work?Nature Biotechnol...

work page doi:10.1137/1.9781611978964.28 2026

Show all 25 references

[21]

51 Sampath K

URL:https://doi.org/10.1609/aaai.v24i1.7684,doi:10.1609/AAAI.V24I1.7684. 51 Sampath K. Kannan, Eugene L. Lawler, and Tandy J. Warnow. Determining the evolutionary tree using experiments.Journal of Algorithms, 21(1):26–50, 1996.doi:10.1006/jagm.1996

doi
[23]

54 Christian Komusiewicz and Johannes Uhlmann

doi: 10.1007/978-3-642-18381-2_29. 54 Christian Komusiewicz and Johannes Uhlmann. Cluster editing with locally bounded modifi- cations.Discrete Applied Mathematics, 160(15):2259–2270,

doi
[24]

Algorithms for hierarchical clustering: an overview

57 Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: an overview. WIREs Data Mining and Knowledge Discovery, 2(1):86–97, 2012.doi:10.1002/widm.53. 58 Fábio Protti, Maise Dantas da Silva, and Jayme Luiz Szwarcfiter. Applying modular de- composition to p...

2012 doi
[35]

Kimes, Yufeng Liu, David Neil Hayes, and James Stephen Marron

52 Patrick K. Kimes, Yufeng Liu, David Neil Hayes, and James Stephen Marron. Statistical significance for hierarchical clustering.Biometrics, 73(3):811–821, 2017.doi:10.1111/biom. 12647. 53 Christian Komusiewicz and Johannes Uhlmann. Alternative parameterizations for cluster e...

2017 doi
[1962]

61 Joe H. Ward. Hierarchical grouping to optimize an objective function.Journal of the American Statistical Association, 58(301):236–244, 1963.doi:10.2307/2282967. A Proof of Proposition 5 Proof. The idea is to set the value ofdist to every edge inA equal to its upper-threshol...

1963 doi
[1967]

Improved approximations for ultrametric violation distance

22 Moses Charikar and Ruiquan Gao. Improved approximations for ultrametric violation distance. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1704–1737. SIAM,

2024
[1975]

15 Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang

doi: 10.1016/0022-2496(75)90028-0. 15 Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Solving the correlation cluster lp in sublinear time. InProceedings of the 57th Annual AC...

doi
[1993]

A robust model for finding optimal evolutionary trees.Algorithmica, 13:155–179, 1995.doi:10.1007/BF01188585

40 Martin Farach, Sampath Kannan, and Tandy Warnow. A robust model for finding optimal evolutionary trees.Algorithmica, 13:155–179, 1995.doi:10.1007/BF01188585. 41 James S. Farris. Estimating phylogenetic trees from distance matrices.The American Naturalist, 106(951):645–668,

1995 doi
[2004]

8 Gabriel Bathie and Guillaume Lagarde

URL:http://dx.doi.org/10.1023/B:MACH.0000033116.57574.95. 8 Gabriel Bathie and Guillaume Lagarde. A(1 +ϵ)-approximation for ultrametric embedding in subquadratic time,
[2005]

Maximizing quadratic programs: Extending Grothendieck’s inequality

25 Moses Charikar and Anthony Wirth. Maximizing quadratic programs: Extending Grothendieck’s inequality. InProceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), pages 54–60. IEEE Computer Society,

2004
[2010]

Fitting tree metrics and ultrametrics in data streams

20 Amir Carmel, Debarati Das, Evangelos Kipouridis, and Evangelos Pipis. Fitting tree metrics and ultrametrics in data streams. InProceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP), volume 299 ofLIPIcs, pages 42:1–42:21. Schloss Da...

2025 doi
[2011]

Aggregating inconsistent information: Ranking and clustering.J

3 Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering.J. ACM, 55:23:1–23:27, November 2008.doi:http://doi.acm.org/ 10.1145/1411509.1411513. 4 Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic fo...

2008
[2014]

04.015,doi:10.1016/J.JCSS.2014.04.015

URL:https://doi.org/10.1016/j.jcss.2014. 04.015,doi:10.1016/J.JCSS.2014.04.015. 44 Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.Kernelization: theory of parameterized preprocessing. Cambridge University Press,

2014 doi
[2015]

34 Peter Damaschke

URL:http://dx.doi.org/10.1007/978-3-319-21275-3. 34 Peter Damaschke. Fixed-parameter enumerability of cluster editing and related problems. Theory Comput. Syst., 46(2):261–283,

doi
[2020]

38 ChenglinFan, BenjaminRaichel, andGregoryVanBuskirk

Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.SWAT.2020.25. 38 ChenglinFan, BenjaminRaichel, andGregoryVanBuskirk. Metricviolationdistance: Hardness and approximation. InProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SO...

2020 doi
[2024]

17 Yixin Cao and Jianer Chen

doi:10.1145/3618260.3649749. 17 Yixin Cao and Jianer Chen. Cluster editing: Kernelization based on edge cuts. InProceedings of the 5th International Symposium on Parameterized and Exact Computation (IPEC 2010), volume 6478 ofLecture Notes in Computer Science, pages 60–71. Springer,

2010
[2025]

6 Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra

doi: 10.1109/FOCS63196.2025.00060. 6 Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra. On non-approximability for quadratic programs. InProceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 206–215. IEEE Computer Society,

2025

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

On the approximability of numerical taxonomy (fitting distances by tree metrics).SIAM Journal on Computing, 28(3):1073–1085, 1999.doi:10.1137/S0097539796309764

1 Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, and Mikkel Thorup. On the approximability of numerical taxonomy (fitting distances by tree metrics).SIAM Journal on Computing, 28(3):1073–1085, 1999.doi:10.1137/S0097539796309764. 2 Nir Ailon and Moses Charikar. Fitting tree metrics: Hierarchical clustering and phylogeny. SIAM Journal on Comput...

doi:10.1137/s0097539796309764 1999

[2] [5]

A $(1+\epsilon)$-Approximation for Ultrametric Embedding in Subquadratic Time

URL:https://arxiv.org/abs/2503.13409,arXiv:2503.13409. 9 Amir Ben-Dor, Ron Shamir, and Zohar Yakhini. Clustering gene expression patterns.Journal of Computational Biology, 6(3/4):281–297,

work page Pith review arXiv

[3] [6]

A golden ratio parameterized algorithm for cluster editing.Journal of Discrete Algorithms, 16:224–233, 2012.doi:10.1016/j.jda.2012.04.001

11 Sebastian Böcker. A golden ratio parameterized algorithm for cluster editing.Journal of Discrete Algorithms, 16:224–233, 2012.doi:10.1016/j.jda.2012.04.001. 12 Sebastian Böcker and Peter Damaschke. Even faster parameterized cluster deletion and cluster editing.Inf. Process. Lett., 111(14):717–721,

work page doi:10.1016/j.jda.2012.04.001 2012

[4] [8]

16 Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl

Association for Computing Machinery.doi:10.1145/3717823.3718181. 16 Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl. Understanding the cluster linear program for correlation clustering. InProceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1605–1616. ACM,

arXiv

[5] [12]

Clustering with qualitative information

23 Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. InProceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), pages 524–533. IEEE Computer Society,

work page 2003

[6] [14]

A2k kernel for the cluster editing problem.Journal of Computer and System Sciences, 78(1):211 – 220, 2012.doi:10.1016/j.jcss.2011.04.001

26 Jianer Chen and Jie Meng. A2k kernel for the cluster editing problem.Journal of Computer and System Sciences, 78(1):211 – 220, 2012.doi:10.1016/j.jcss.2011.04.001. 27 Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, and Mikkel Thorup. Fitting distances by tree metrics minimizing the total error within a constant factor. J. ACM...

work page doi:10.1016/j.jcss.2011.04.001 2012

[7] [15]

30 Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman

URL: https://doi.org/10.1137/22m1520190,doi:10.1137/22M1520190. 30 Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman. Handling correlated rounding error via preclustering: A 1.73-approximation for correlation clustering. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1082–1104, 2023.doi:10.1109/FOCS57990.202...

arXiv

[8] [17]

Tree violation distance under constraints

35 Debarati Das, Evangelos Kipouridis, and Joachim Spoerhase. Tree violation distance under constraints. InProceedings of the 2026 SIAM Symposium on Simplicity in Algorithms (SOSA), pages 355–364, 2026.doi:10.1137/1.9781611978964.28. F.V. Fomin, P.A. Golovach, and Y. More 29 36 Patrik D’haeseleer. How does gene expression clustering work?Nature Biotechnol...

work page doi:10.1137/1.9781611978964.28 2026