{"id":"b37ccb4d-2ca5-4b0f-b189-d7470ab9a939","arxiv_id":"2608.09546","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Ultrametric Violation Distance, parameterized by the number k of edited distances, admits a kernel with O(k^2) points and an FPT algorithm running in O(9^k k n^2) time.","lead":"This paper provides a polynomial-size compression and a faster exact algorithm for the problem of editing the fewest pairwise distances so that they form a valid ultrametric, i.e., a hierarchical family tree. The results settle a natural open question in parameterized complexity for this fitting problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"FPT running-time analysis rests on Claim 24's assertion that a D_i edge can only be decreased; the proof never formalizes the branch-consistency invariant, so the 9^k leaf bound is not yet established.","rationale":"The reader's weakest-assumption selection matches my own stress-test: Claim 24 is the pivotal step in the FPT analysis, and its proof is the least developed part of the paper. After reconstructing the intended argument, I find no concrete counterexample: increasing an edge in D_i does not change its status in the auxiliary graph G_i (it remains a non-edge), so it cannot repair a violated triangle at level i, and any increase needed at a higher level would already have been performed in the branch that follows a valid solution. Thus the claim is likely true, but only under a branch-consistency invariant that the paper never states. Because the proof of Lemma 23 and the branching cases depend on this invariant, the write-up is not yet fully rigorous, and the conditional verdict is appropriate. I did not find a fatal flaw in the kernelization; the counting in Claim 19 is consistent once one notes that a triangle w.r.t. an edge is determined by its third vertex, and the irrelevant-vertex removal can be repaired by observing that cross-layer edges need not be edited in any optimal solution. The 'asymptotically tight' phrasing in the abstract and Section 1.1 is an overclaim, since only an ETH-based subexponential lower bound is shown, not a lower bound on the base 9, but this is a presentation issue rather than a correctness issue for the theorems. Overall, the central claims are plausible and the concerns are about rigor and presentation, not about a demonstrated false statement. The concrete brute-force test above would settle whether the Claim 24 concern actually lands; if it passes, the proof can be repaired by formalizing the invariant without changing the theorems.","tokens_in":27374,"tokens_out":45072,"duration_ms":428416,"concrete_test":"Implement Algorithm 1 and exhaustively verify it on all CUVD instances with |X|≤5, integer distances and thresholds in {1,...,6}, and k≤2, comparing its yes/no answer and reported edit cost against a brute-force search over all edit sets (using Proposition 5 to test feasibility). Instrument the search to record, for each successful root-to-leaf path, the sequence of operations on each edge; check that no edge is increased after being decreased and that the total measure charged to each edited edge is at most 2. If any instance produces a wrong answer, or any solution path charges more than 2 units to an edge that is edited only once, Claim 24's invariant is refuted and Theorem 2's running-time analysis collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2's running time O(9^k·k·|X|^2) is obtained from a branching tree with at most 3^{2k} leaves, where the measure µ=2k-|U| charges at most 2 units per edited edge. That charge is justified only if, along every root-to-leaf path, an edge is edited monotonically: an edge whose current distance is d_i at level i may be decreased (marked and later finalized), but it never needs to be both increased and decreased. This is exactly what Claim 24 asserts, but its proof is a two-sentence induction that does not track branch-dependent state. Concretely, an edge e with original distance d_i could, in another branch, have been increased to d_j (j>i) while processing a higher level; if that did not happen in the current branch, e is in D_i at level i, and Claim 24 says the only remaining option is to decrease it. The proof does not explain why, in a branch that is consistent with some valid solution, no solution can require increasing such an e at level i. The underlying reason is plausibly correct: increasing e does not change its status as a non-edge in the auxiliary graph G_i, so it cannot fix a violated triangle at level i, and any increase needed at a higher level would already have been taken in the solution-following branch. But this invariant is not stated or proved, and the branching cases in the 'Branching Cases Subroutine' silently rely on it. If the invariant failed, the branch cases would be non-exhaustive, and the measure could overcount an edge's cost, invalidating the 3^{2k} leaf bound. This is the least secure step in the FPT part of the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":27700,"tokens_out":39129,"duration_ms":355227,"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":[{"comment":"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.","section":"4, Claim 24"},{"comment":"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.","section":"4, Running Time Analysis"},{"comment":"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.","section":"3, Claim 19"}],"minor_comments":[{"comment":"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.","section":"3, Reduction Rule 5"},{"comment":"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.","section":"3, Claim 20"},{"comment":"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.","section":"4, Algorithm 1"},{"comment":"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.","section":"1.2 and Figure 2"},{"comment":"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.","section":"3, end of Theorem 1 proof"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within scope for a theory journal, and the kernelization ideas are likely correct after the counting step in Claim 19 is clarified. The main obstacle is the FPT section: Claim 24 is a genuine proof gap, and the linear-time cluster update used for the running time is unproven. I do not see grounds for rejection, but I would not accept before these two points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nTwo 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.\n\nWho 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.","headline":"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.","tokens_in":28272,"tokens_out":2532,"would_cite":true,"duration_ms":25844,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Ultrametric fitting with few changed distances admits a kernel of O(k^2) points and a single-exponential 9^k algorithm.","keywords":["Ultrametric","Violation Distance","Kernelization","Fixed-Parameter Tractability","Cluster Editing","Hierarchical Clustering","ℓ0-norm","Divisive Branching"],"falsifier":"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.","tokens_in":27193,"feed_emoji":"🌳","tokens_out":10218,"duration_ms":81593,"temperature":0.7,"pith_summary":"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.","feed_headline":"Polynomial kernel and 9^k algorithm for ultrametric fitting","feed_subtitle":"Reducing any instance to O(k^2) points, then solving in 9^k·n^{O(1)} time.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the $k^{O(k)}n^{O(1)}$ algorithm for Metric Violation Distance that, via tropicalization, gives the previously known FPT baseline for Ultrametric Violation Distance.","marker":"[37]"},{"why":"Introduces the $\\ell_0$-norm Ultrametric Violation Distance problem and provides the tropicalization reduction (Corollary 5.16) connecting it to metric repair.","marker":"[29]"},{"why":"Gives the Ultrametric Matrix Sandwich algorithm that Proposition 5 adapts to test in polynomial time whether a guessed set of edited edges yields an ultrametric.","marker":"[40]"},{"why":"Proves the ETH-based lower bound for Cluster Editing that transfers to rule out subexponential algorithms for CUVD.","marker":"[43]"},{"why":"Provides a second ETH-based lower bound for Cluster Editing, cited alongside [43] for the tightness of the exponential dependence.","marker":"[54]"},{"why":"Gives the 2k-vertex kernel for Cluster Editing, the special case against which the kernelization target is calibrated.","marker":"[26]"}],"fun_headline_variants":["Ultrametric fitting: kernel in O(k^2), solve in 9^k","Polynomial kernel and 9^k FPT for ultrametric fitting","Tight 9^k algorithm for ultrametric violation distance","O(k^2) kernel and single-exponential FPT for ultrametric data","Ultrametric violation: polynomial kernel, 9^k time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Ultrametric fitting: kernel in O(k^2), solve in 9^k","Polynomial kernel and 9^k FPT for ultrametric fitting","Tight 9^k algorithm for ultrametric violation distance","O(k^2) kernel and single-exponential FPT for ultrametric data","Ultrametric violation: polynomial kernel, 9^k time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000417,"raw_usage":{"total_tokens":2203,"prompt_tokens":1053,"completion_tokens":1150,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":669,"completion_tokens_details":{"reasoning_tokens":1052}},"tokens_in":669,"tokens_out":1150,"duration_ms":9830,"temperature":1.0,"reasoning_tokens":1052,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:25:19.647645+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}