{"id":"1cb1f173-aca6-4a65-844c-b803569d013b","arxiv_id":"2506.11704","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The minimum isometric-universal graph for two forests can be computed in polynomial time, while the problem for three forests is NP-complete.","lead":"This paper proves that the smallest graph preserving all distances between two input trees or forests can be found in polynomial time. It also shows the problem becomes NP-complete for three forests, and that greedy pair-by-pair strategies cannot reach the optimum for some three-tree families.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"NP-hardness lower bound rests on the unproved 'we can check' in Claim 25 Sub-case 1.2; a one-vertex packing of an unmatched F(w) would break the |V(F_X)|+n threshold.","rationale":"I read the paper as making two central contributions: a polynomial algorithm for two forests and NP-completeness for three forests. The polynomial side is well supported: Theorem 6's contraction argument is detailed, Claims 8 and 9 are fleshed out, Theorem 1's reduction to maximum-weight bipartite matching is sound, and the only flaw is a typographical log^2/log slip in the proof of Theorem 11 (Theorem 10 states O(n^{5/2} log n), so taking f(n)=C n^{5/2} log n makes the stated O(n^{7/2} log n) correct). The NP-hardness upper bound is constructive and correct. The lower bound, however, hinges on Claim 25's case analysis. Sub-case 1.2 is the only place where the text explicitly defers a check with 'we can check' and 'one can reproduce', and it is exactly the configuration needed to force the second extra vertex. A single counterexample to that sub-case would allow a non-matching instance to fit in the threshold, destroying Claim 21. This is not an internal inconsistency in the claimed theorem, but an incompleteness in the proof as written, so the reader's CONDITIONAL verdict with medium correctness risk is appropriate. I recommend no change to the verdict, with the condition being that Sub-case 1.2 be proved (or the reduction modified) and the log-factor in Theorem 11's proof be corrected.","tokens_in":26883,"tokens_out":18689,"duration_ms":167483,"concrete_test":"Enumerate small instances to falsify or support Sub-case 1.2: fix n=3 (so 2n=6 star types, |V(F(w))|=13) and generate all admissible F(x0) trees for T(x0) of size 2 and 3 with all possible star orders. For each w not appearing in T(x0), use a bounded-treewidth (or CP-SAT) solver to decide whether there exists a tree U = F(x0) plus one new vertex c, with c not in the image of F(x0), such that F(x0) and F(w) both embed as connected subgraphs (equivalently, isometric subgraphs, since U is a tree). If such a U exists for any instance, Claim 25 Sub-case 1.2 is false and the threshold in Claim 21 fails. If none exists, run the same check for n=4 as a second data point and then supply the missing analytic argument for the 'we can check' step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that is least secure is the lower-bound direction of Claim 21 in Theorem 19. The threshold |V(F_X)|+n separates yes-instances from no-instances of 3D-Matching: Claim 25 must prove that a component whose triple (x0,y0,z0) is not in T costs at least two extra vertices. The decisive configuration is Sub-case 1.2, where the center c of F(w) is assumed not to lie in Fhat(x0) and one assumes |V(U)| ≤ |V(F(x0))|+1. The proof then asserts that all neighbors of c in U 'must be included in the neighbors of the center c' of some copy of S(w') in Fhat(x0)', adding 'If not, we can check that some distances in Fhat(x0) or in Fhat(w) would be shortened', and that 'one can reproduce the same analysis as in Claim 24' with w'>w. Neither assertion is demonstrated, and Claim 24 is a different, simpler argument that only establishes one extra vertex, not two. If a single new vertex c can be attached to Fhat(x0) so that an unmatched S(w) plus its claw embeds isometrically, then |V(U(x0))| = |V(F(x0))|+1, the summed lower bound becomes |V(F_X)|+n, and the 'only if' direction of Claim 21 fails, invalidating the NP-completeness reduction. This is separate from the harmless log^2/log typo in Theorem 11.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the minimum number of vertices of an isometric-universal graph for two input trees or forests. For two trees, it proves that a minimum and minimal isometric-universal graph is a tree (Theorem 6), and uses the Gupta--Nishimura minimum-supertree algorithm to compute such a graph in O(n^{5/2} log n) time (Theorem 10). For two forests, it combines Theorem 10 with a component-reduction to the Assignment Problem (Theorem 1) to obtain an O(n^{7/2} log n) algorithm (Theorem 11). On the negative side, the paper proves that the three-forest decision problem is NP-complete (Theorem 19) via a reduction from 3D-Matching, that there are triples of trees with no minimum isometric-universal tree (Theorem 12), that greedy strategies cannot always build a minimum isometric-universal graph or tree (Proposition 16), and that k-isometric-universal graphs for two trees need not be trees for k below roughly n/3 (Theorem 17). The central positive algorithm and structural theorem are presented in detail; the NP-completeness reduction contains a significant gap in its lower-bound case analysis.","tokens_in":27181,"tokens_out":22548,"duration_ms":192139,"significance":"If the results are correct, the paper makes a valuable contribution to the theory of distance-preserving embeddings and universal graphs. Theorem 6 is the strongest structural ingredient: it connects minimum isometric-universal graphs for two trees to minimum supertrees, and the proof by cycle contraction is interesting in its own right. The reduction from two forests to a weighted bipartite matching problem is clean and gives a non-trivial polynomial algorithm. The complexity dichotomy between two forests (polynomial) and three forests (NP-complete) is a meaningful boundary result, and the paper also gives a credible negative result for greedy strategies. The paper is theorem-driven; there is no code or experimental validation, but the style is appropriate for the claimed results. The main obstacle to accepting Theorem 19 is the unproved case analysis in Claim 25, on which the NP-completeness lower bound depends.","major_comments":[{"comment":"In the proof of Theorem 11, the function f is set to f(n) = C n^{5/2} log^2 n, whereas Theorem 10 supplies only the bound O(n^{5/2} log n). With the stated log^2 factor, the term r f(2n) is O(n^{7/2} log^2 n), so the displayed conclusion O(n^{7/2} log n) does not follow. This is a load-bearing inconsistency in the running-time claim of Theorem 11, even though it does not affect polynomiality. The fix is straightforward: take f(n) = C n^{5/2} log n, which is compatible with Theorem 10 and is superlinear, and then the computation yields O(n^{7/2} log n). Please correct this point in the proof or revise the theorem statement.","section":"Section 2.3, Theorem 11"},{"comment":"The lower-bound direction of Claim 21 rests on Claim 25, and Sub-case 1.2 is the decisive configuration: the center c of F(w) is assumed not to lie in Fhat(x0), and the proof assumes |V(U)| <= |V(F(x0))| + 1. The manuscript then asserts that all neighbors of c in U 'must be included in the neighbors of the center c' of some copy of S(w') in Fhat(x0)', adding 'If not, we can check ...' and 'One can reproduce the same analysis as in Claim 24 ...'. These assertions are not demonstrated. Moreover, Claim 24 only establishes that Fhat(x0) union Fhat(w) contains at least one extra vertex, whereas Sub-case 1.2 must rule out exactly one extra vertex and prove that at least two are needed. The dangerous scenario — a single new vertex c whose independent set of 3w+4 neighbors is placed inside the neighborhood of a star center of Fhat(x0) — is precisely the case that the proof does not analyze. Since the threshold |V(F_X)| + n in Claim 21 depends on this lower bound, the NP-completeness reduction is incomplete without a full case analysis of Sub-case 1.2.","section":"Section 3.4, Claim 25, Sub-case 1.2"},{"comment":"In Case 2 of Claim 25, the argument that two distinct extra vertices are required is compressed into the sentence 'These two vertices are not the same, otherwise the distance between c and c' would not be correct.' This needs a detailed justification, in particular when one of c or c' is itself outside Fhat(x0). The proof must show that no single vertex can simultaneously supply the missing neighbor for the claw of F(y0) and the missing neighbor for the claw of F(z0), and that the relevant distances in Fhat(x0) and Fhat(y0), Fhat(z0) are preserved in all subcases. As written, this is another load-bearing gap in the same lower-bound argument.","section":"Section 3.4, Claim 25, Case 2"}],"minor_comments":[{"comment":"In the displayed inequality before the conclusion of Claim 15, the expression |V(Rhat T_i,Rhat T_j)| should be |V(Rhat T_i ∩ Rhat T_j)|; the intersection symbol is missing.","section":"Section 3.1, Claim 15"},{"comment":"In the sentence defining p(w,w'), the text says 'the unique vertex of the path between the centers c(w) and c(w)'; the second occurrence should be c(w').","section":"Section 3.4, Figure 13 caption"},{"comment":"The statement of Theorem 12 says the trees have 'pathwidth 3 two'; this should read 'pathwidth two'.","section":"Section 3.1, Theorem 12"},{"comment":"The proof of Proposition 16 is informal in several places, relying on phrases such as 'It is not difficult to see' and 'the only way to get three stars'. Since this proposition is presented as a formal result, please state explicit conditions on the parameters r and s and give a complete argument that the relevant distance sets force a fourth star in every greedy execution.","section":"Section 3.2, Proposition 16"}],"recommendation":"major_revision","confidential_remarks":"The positive results — Theorem 6, the two-tree algorithm, and the component reduction — are solid and would justify publication on their own. The main risk is the NP-completeness proof of Theorem 19, specifically the lower-bound case analysis in Claim 25. The log-factor inconsistency in Theorem 11 is a trivial fix. If the authors can supply a complete proof of Claim 25, the paper should be acceptable; if that gap cannot be closed, the NP-completeness claim would need to be removed or weakened, and the remaining paper would still contain substantial contributions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the paper. The headline is simple: the two-forest polynomial result and the three-forest NP-completeness result are real, and the structural core—Theorem 6, that a minimum minimal isometric-universal graph for two trees is a tree—is what gives the paper its value. The contraction proof of Theorem 6 is detailed and I did not find a hole in it. That theorem, combined with the component-reduction argument, yields the forest algorithm in a clean way.\n\nThe NP-hardness reduction is more of a mixed bag. The upper-bound direction is fine. The lower-bound direction (Claims 21-25) is genuinely load-bearing. The reader flagged two soft spots, and both are real, though one is minor. The log-factor in the proof of Theorem 11: the proof sets f(n)=C n^{5/2} log^2 n and concludes O(n^{7/2} log n). That is a gap as written; either set f(n)=C n^{5/2} log n (matching Theorem 10) or change the forest bound to O(n^{7/2} log^2 n). The abstract says log n, so this is presumably a typo, but it needs fixing.\n\nThe larger issue is Claim 25, Sub-case 1.2. The stress-test note worried about an unmatched F(w) being packed into F(x0) with one extra vertex, breaking the |V(F_X)|+n threshold. I think that specific attack fails, because F(w) is not just a subdivided star: it carries a claw attached to the center. If the center c is the single extra vertex, the claw center and its two further leaves must also appear, and they cannot be mapped to vertices of Fhat(x0) without creating shortcuts in Fhat(x0) or Fhat(w). So the lower bound likely survives. But the written proof of that sub-case is too compressed: 'we can check' and 'one can reproduce the same analysis as in Claim 24' are not adequate for a result this central. This is a fixable exposition gap, not a clear fatal flaw, but it is exactly where a referee should push.\n\nI also want to give credit: the paper handles the relation to Rautenbach-Werner and the self-cited [GJ24] properly. No parameter fitting, no invented entities. It ships no code, but the algorithmic content is in cited black boxes.\n\nBottom line: this paper deserves a serious referee. It has one clean structural theorem, a sensible reduction to the assignment problem, and a nontrivial NP-completeness proof. The revisions I would ask for are a corrected log factor and a rewritten Sub-case 1.2 with the claw argument explicit. The audience is graph algorithms and distance-preserving embeddings; a reader in that area gets real value.\n\nRecommendation: accept for review, with the expectation of minor-to-moderate revision.","headline":"A solid, citable paper: two-forest universality is polynomial via a clean tree-structure theorem, three-forest is NP-complete, though the NP-hardness lower bound needs a rewrite of one sub-case.","tokens_in":27709,"tokens_out":9324,"would_cite":true,"duration_ms":87831,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C05","05C12","05C85","68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A minimum isometric-universal graph for two trees can be computed in polynomial time, but the same problem for three forests is NP-complete.","keywords":["isometric-universal graph","isometric subgraph","distance-preserving embedding","minimum supertree","assignment problem","3D-Matching reduction","NP-completeness","k-isometric-universal graph"],"falsifier":"Take a 3D-Matching instance with no perfect matching (say $n = 2$) and compute, by exhaustive search over embeddings, the true minimum number of vertices of an isometric-universal graph for the three constructed forests; the reduction predicts this number is strictly greater than $|V(F_X)| + n$. Finding a host at or below that threshold would refute the NP-completeness proof's main threshold claim.","tokens_in":26678,"feed_emoji":"🌳","tokens_out":13545,"duration_ms":123184,"temperature":0.7,"pith_summary":"The paper asks how small a graph can be while containing two given trees (or forests) with all distances preserved. It proves that for two trees with at most $n$ vertices this smallest 'isometric-universal' graph can be computed in $O(n^{5/2} \\log n)$ time, and for two forests in $O(n^{7/2} \\log n)$ time. The key structural reason is that a smallest such graph for two trees is always itself a tree, so the problem reduces to the classical minimum supertree problem. The paper then shows the tractability stops at three: deciding whether three forests admit an isometric-universal graph with $t$ vertices is NP-complete, and some triples of trees have no minimum universal graph that is a tree, which rules out simple greedy merging strategies.","feed_headline":"Two-tree universal graphs solved; three forests NP-complete","feed_subtitle":"Smallest distance-preserving supergraph for two forests is polynomial; a third forest breaks the pattern.","key_machinery":"Two mechanisms carry the argument. The positive side rests on a structural theorem: every minimum and minimal isometric-universal graph for two trees is a tree, proved by taking a shortest cycle in a candidate host and contracting two neighbors so that distances inside both embedded trees are unchanged. This converts the two-tree problem into the classical minimum-super-tree problem, for which a known $O(n^{5/2} \\log n)$ algorithm applies. For two forests, a component-assignment step builds an auxiliary complete bipartite graph whose edge weights are the numbers of vertices the corresponding tree components can share in a minimum pair solution; a maximum-weight maximum matching then selects the global host, with the matching computed by weight-scaling and integer-priority-queue methods. The hardness side uses a gadget of subdivided stars $K_{1,3w+3}$ with claws attached, arranged along paths in an order that encodes a 3D-Matching instance; the threshold $|V(F_X)| + n$ separates solvable from unsolvable instances.","core_discovery":"The paper's central claim is a dichotomy. For the family of two forests with at most $n$ vertices each, a minimum isometric-universal graph—a host graph in which both forests embed as distance-preserving (isometric) subgraphs—can be built in polynomial time, $O(n^{7/2} \\log n)$, and $O(n^{5/2} \\log n)$ when both inputs are trees. This rests on the structural theorem that every minimum and minimal isometric-universal graph of two trees is itself a tree, so the two-tree case reduces to the minimum supertree problem with its known polynomial algorithm. For three forests, however, the decision question 'is there an isometric-universal graph with $t$ vertices?' is NP-complete, proved by a reduction from 3D-Matching using subdivided stars with claws; the same hardness holds when the host is required to be a forest. Moreover, there are infinite families of three trees for which no minimum isometric-universal graph is a tree, and no greedy strategy that repeatedly merges using an optimal two-graph oracle can be optimal.","pith_inferences":["The 3D-Matching reduction is threshold-based, so the NP-hardness likely extends to decision variants asking for a universal graph with at most $t$ vertices, and may even obstruct constant-factor approximation.","The same component-weight matching scheme could be ported to other containment notions—topological minors, induced subgraphs—whenever per-pair optimal hosts are computable.","The paper leaves open the arboricity—the minimum number of edge-disjoint forests needed to cover the edges—of minimum universal graphs for $t > 2$ trees; the family constructed in its Theorem 12 is a natural first test case for whether arboricity 2 is always achievable for triples.","A brute-force verification of the threshold on the smallest reduction instances ($n = 2$) would give an independent check of the informally asserted subcases in Claims 24–25 before the full case analysis is filled in."],"forward_implications":["A minimum isometric-universal graph for two trees is always a tree, so any minimum-super-tree algorithm solves the two-tree case.","The two-forest case reduces to one assignment problem over component pairs, yielding the $O(n^{7/2} \\log n)$ running time.","For three forests the decision problem is NP-complete, even when the host graph is required to be a forest and the three input forests are tree-like (pathwidth at most two).","There are triples of trees for which no minimum universal graph is a tree, so greedy sequential merging with an optimal two-graph oracle cannot in general reach the optimum.","For $k$-isometric-universal graphs—hosts preserving distances up to $k$—the tree-structure guarantee fails for $k < (n-8)/3$, so the polynomial behavior is specific to full isometric containment ($k = \\infty$)."],"supporting_citations":[{"why":"Supplies the O(n^{5/2} log n) minimum-super-tree algorithm; the two-tree result reduces to it through the tree-structure theorem.","marker":"[GN98]"},{"why":"Provides the weight-scaling algorithm for maximum-weight maximum bipartite matching used in the component-assignment step.","marker":"[RT12]"},{"why":"Integer priority queues that combine with the weight-scaling algorithm to yield the alternative matching-time bound.","marker":"[Tho04]"},{"why":"Source of the NP-complete 3D-Matching problem (with each element in at most three triples) from which the hardness reduction is built.","marker":"[GJ79]"},{"why":"Previously claimed the forest-restricted form of the NP-completeness statement; the paper presents its own proof of the same restriction.","marker":"[RW24]"},{"why":"Established the notion of isometric-universal graphs for large families of graphs and provides the framework the paper extends.","marker":"[EGG21]"},{"why":"Defines distance-preserving embeddings, the underlying containment relation for isometric subgraphs.","marker":"[Win83]"}],"fun_headline_variants":["Two forests fit fast; three forests are hard","Minimum universal graph: two polynomial, three NP-complete","Polynomial for two forests, NP-complete for three","Two-tree universal graph: polynomial; three-tree: NP-complete"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The NP-hardness lower bound relies on the case analysis of Claims 24–25 asserting that every way of packing the constructed star-and-claw trees into one component forces at least the claimed number of extra vertices; several subcases are asserted informally rather than proved step by step.","fun_headline_variants_meta":{"raw":{"variants":["Two forests fit fast; three forests are hard","Minimum universal graph: two polynomial, three NP-complete","Polynomial for two forests, NP-complete for three","Two-tree universal graph: polynomial; three-tree: NP-complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000589,"raw_usage":{"total_tokens":2763,"prompt_tokens":945,"completion_tokens":1818,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":1751}},"tokens_in":561,"tokens_out":1818,"duration_ms":15576,"temperature":1.0,"reasoning_tokens":1751,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:05:33.936195+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a 3D-Matching instance with no perfect matching (say $n = 2$) and compute, by exhaustive search over embeddings, the true minimum number of vertices of an isometric-universal graph for the three constructed forests; the reduction predicts this number is strictly greater than $|V(F_X)| + n$. Finding a host at or below that threshold would refute the NP-completeness proof's main threshold claim.","supporting_citations":[],"review_version":1}