Isometric-Universal Graphs for Trees

Cyril Gavoille; Edgar Baucher; Fran\c{c}ois Dross

REVIEW 3 major objections 4 minor 20 references

Isometric-Universal Graphs for Trees

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A minimum isometric-universal graph for two trees can be computed in polynomial time, but the same problem for three forests is NP-complete.

desk verdict 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. read the letter →

arxiv 2506.11704 v2 pith:LGCCRLI2 submitted 2025-06-13 cs.DS

Edgar Baucher , François Dross , Cyril Gavoille This is my paper · ORCID

classification cs.DS MSC 05C0505C1205C8568Q1768Q25

keywords isometric-universalgraphisometricsubgraphdistance-preservingembeddingminimumsupertreeassignmentproblem3D-MatchingreductionNP-completenessk-isometric-universal

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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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$).

Reading between the lines

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

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.

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

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.

The 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.

The 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.

I 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.

Bottom 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.

Recommendation: accept for review, with the expectation of minor-to-moderate revision.

Referee Report

3 major / 4 minor

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.

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 (3)

[Section 2.3, Theorem 11] 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 3.4, Claim 25, Sub-case 1.2] 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 3.4, Claim 25, Case 2] 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.

minor comments (4)

[Section 3.1, Claim 15] 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 3.4, Figure 13 caption] 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 3.1, Theorem 12] The statement of Theorem 12 says the trees have 'pathwidth 3 two'; this should read 'pathwidth two'.
[Section 3.2, Proposition 16] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: load-bearing steps are proved in-paper or use external algorithms; the only flagged gap (Claim 25, 'we can check') is an omitted proof, not an input-output circularity.

full rationale

Walked the claimed derivation chain. In Theorem 1, the component graphs S(G_i,H_j) are computed independently for each connected component pair, and Claims 3 and 5 prove from minimality that a minimum universal graph for two forests corresponds to a maximum-weight maximum matching in an auxiliary bipartite graph; the vertex-count formula |V(U)|=|V(G)|+|V(H)|-w(D) is derived, not assumed. Theorem 6 is a self-contained contraction argument: if a minimum and minimal universal graph for two trees had a shortest cycle, Claims 7-9 show that contracting the two neighbors of the cycle preserves all distances within each embedded tree, producing a smaller universal graph and a contradiction; no equation is used as its own premise. Theorem 10 invokes the external Gupta-Nishimura minimum-super-tree algorithm [GN98], and uses only the elementary fact that in a tree the unique path between two vertices of a subgraph is the subgraph path, so a supertree is automatically isometric-universal. The two-forest result (Theorem 11) is a direct composition of Theorem 1 with the external two-tree algorithm, plus the standard Ramshaw-Tarjan assignment algorithm. The negative results are explicit constructions and reductions: Theorem 12 bounds pairwise intersections of embedded stars, and Theorem 19 reduces from 3D-Matching with a threshold on |V(U)|. The lower-bound direction of Claim 21 contains informal assertions in Claim 25 Sub-case 1.2, notably 'If not, we can check that some distances in Fhat(x0) or in Fhat(w) would be shortened' and 'One can reproduce the same analysis as in Claim 24'; this is an omitted-proof correctness risk, not circularity, because the inequality |V(U(x0))|>|V(F(x0))|+1 is a claimed combinatorial fact about possible isometric embeddings, not an input that is renamed as the output. The self-citations [GJ24] and [EGG21] are contextual and do not support any load-bearing derivation. Accordingly no step reduces by construction to its own inputs; the derivation chain is self-contained or rests on independently stated external algorithms.

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

The central claims rest on explicit constructions and standard external algorithms. No parameters are fitted to data, and no new entities are postulated. The paper is self-contained except for the cited black-box algorithms and the standard NP-completeness source problem.

assumptions (5)

standard math Gupta-Nishimura [GN98, Theorem 9.6] computes a minimum supertree of two trees with at most n vertices in O(n^{5/2} log n).
Used as a black box in Theorem 10 to obtain the polynomial algorithm for two trees.
standard math Ramshaw-Tarjan [RT12] and Thorup [Tho04] solve the assignment problem (maximum matching of maximum weight in a bipartite graph) within the stated time bounds.
Used in Theorem 1 to combine component-wise universal graphs.
standard math In a tree, the three paths between any three vertices meet in exactly one vertex.
Used in Claim 9 of Theorem 6 to derive distance equalities.
standard math 3D-Matching is NP-complete even when each element belongs to at most three triples [GJ79].
Used as the source problem in the reduction of Theorem 19.
domain assumption Distances between vertices in different connected components of an input graph are infinite, and an isometric embedding must preserve them.
This justifies the component-wise decomposition in Theorem 1 and Claim 22.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Isometric-Universal Graphs for Trees." pith.science (2026). https://pith.science/paper/LGCCRLI2

@misc{pith2026250611704,
  author       = {Pith},
  title        = {Pith review of: Isometric-Universal Graphs for Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LGCCRLI2}},
  note         = {Machine review of arXiv:2506.11704}
}

abstract

We consider the problem of finding the smallest graph that contains two input trees each with at most $n$ vertices preserving their distances. In other words, we look for an isometric-universal graph with the minimum number of vertices for two given trees. We prove that this problem can be solved in time $O(n^{5/2}\log{n})$. We extend this result to forests instead of trees, and propose an algorithm with running time $O(n^{7/2}\log{n})$. As a key ingredient, we show that a smallest isometric-universal graph of two trees essentially is a tree. Furthermore, we prove that these results cannot be extended. Firstly, we show that deciding whether there exists an isometric-universal graph with $t$ vertices for three forests is NP-complete. Secondly, we show that any smallest isometric-universal graph cannot be a tree for some families of three trees. This latter result has implications for greedy strategies solving the smallest isometric-universal graph problem.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 11 canonical work pages

[1]

F. N. Abu-Khzam , Maximum common induced subgraph parameterized by vertex cover , Information Processing Letters, 114 (2014), pp. 99--103. doi : http://doi.org/10.1016/j.ipl.2013.11.007 10.1016/j.ipl.2013.11.007

doi:10.1016/j.ipl.2013.11.007 2014
[2]

F. N. Abu-Khzam, \'E . Bonnet, and F. Sikora , On the complexity of various parameterizations of common induced subgraph isomorphism , Theoretical Computer Science, 697 (2017), pp. 69--78. doi : http://doi.org/10.1016/j.tcs.2017.07.010 10.1016/j.tcs.2017.07.010

doi:10.1016/j.tcs.2017.07.010 2017
[3]

Bollob \'a s, D

B. Bollob \'a s, D. Coppersmith, and M. Elkin , Sparse distance preservers and additive spanners , SIAM Journal on Discrete Mathematics, 19 (2006), pp. 1029--1055. doi : http://doi.org/10.1137/S0895480103431046 10.1137/S0895480103431046

doi:10.1137/s0895480103431046 2006
[4]

Bergold, V

H. Bergold, V. Ir s i c , R. Lauff, J. Orthaber, M. Scheucher, and A. Wesolek , Subgraph-universal planar graphs for trees , Tech. Rep. http://arxiv.org/abs/10.48550/arXiv.2409.01678 2409.01678 [quant-ph] , arXiv, September 2024

arXiv doi:10.48550/arxiv.2409.01678
[5]

Bunke, X

H. Bunke, X. Jiang, and A. Kandel , On the minimum common supergraph of two graphs , Computing, 65 (2000), pp. 13--25. doi : http://doi.org/10.1007/PL00021410 10.1007/PL00021410

work page doi:10.1007/pl00021410 2000
[6]

Bodini , On the minimum size of a contraction-universal tree , in 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol

O. Bodini , On the minimum size of a contraction-universal tree , in 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 2573 of Lecture Notes in Computer Science, Springer, June 2002, pp. 25--34. doi : http://doi.org/10.1007/3-540-36379-3_3 10.1007/3-540-36379-3_3

work page doi:10.1007/3-540-36379-3_3 2002
[7]

Bodwin , New results on linear size distance preservers , SIAM Journal on Computing, 50 (2021), pp

G. Bodwin , New results on linear size distance preservers , SIAM Journal on Computing, 50 (2021), pp. 662--673. doi : http://doi.org/10.1137/19M123662X 10.1137/19M123662X

doi:10.1137/19m123662x 2021
[8]

Coppersmith and M

D. Coppersmith and M. Elkin , Sparse source-wise and pair-wise distance preservers , SIAM Journal on Discrete Mathematics, 20 (2006), pp. 463--501. doi : http://doi.org/10.1137/S0895480104445319 10.1137/S0895480104445319

work page doi:10.1137/s0895480104445319 2006

Show all 20 references

[9]

F. R. Chung, R. L. Graham, and J. Shearer , Note: U niversal caterpillars , Journal of Combinatorial Theory, Series B, 31 (1981), pp. 348--355. doi : http://doi.org/10.1016/0095-8956(81)90037-X 10.1016/0095-8956(81)90037-X

1981 doi
[10]

Dujmovi \'c , L

V. Dujmovi \'c , L. Esperet, C. Gavoille, G. Joret, P. Micek, and P. Morin , Adjacency labelling for planar graphs (and beyond) , Journal of the ACM, 68 (2021), pp. Article No. 42, pp. 1--33. doi : http://doi.org/10.1145/3477542 10.1145/3477542

2021 doi
[11]

Esperet, C

L. Esperet, C. Gavoille, and C. Groenland , Isometric universal graphs , SIAM Journal on Discrete Mathematics, 5 (2021), pp. 1224--1237. doi : http://doi.org/10.1137/21M1406155 10.1137/21M1406155

2021 doi
[12]

Esperet, G

L. Esperet, G. Joret, and P. Morin , Sparse universal graphs for planarity , Journal of the London Mathematical Society, 108 (2023), pp. 1333--1357. doi : http://doi.org/10.1112/jlms.12781 10.1112/jlms.12781

2023 doi
[13]

M. R. Garey and D. S. Johnson , Computers and Intractability - A Guide to the Theory of NP -Completeness , W.H. Freeman, 1979

1979
[14]

Gavoille and A

C. Gavoille and A. Jacques , Compact universal graphs for small families of graphs , 2024. In preparation

2024
[15]

Gawrychowski, F

P. Gawrychowski, F. Kuhn, J. opusza \'n ski, K. Panagiotou, and P. Su , Labeling schemes for nearest common ancestors through minor-universal trees , in 29th Symposium on Discrete Algorithms (SODA), ACM-SIAM, 2018, pp. 2604--2619. doi : http://doi.org/10.1137/1.9781611975031.1...

2018 doi
[16]

Gupta and N

A. Gupta and N. Nishimura , Finding largest subtrees and smallest supertrees , Algorithmica, 21 (1998), pp. 183--210. doi : http://doi.org/10.1007/PL00009212 10.1007/PL00009212

1998 doi
[17]

Ramshaw and R

L. Ramshaw and R. E. Tarjan , A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs , in 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, October 2012, pp. 581--590. doi : http://doi.org/10.1109/FOCS.2...

2012 doi
[18]

Rautenbach and F

D. Rautenbach and F. Werner , Induced subforests and superforests , Tech. Rep. http://arxiv.org/abs/2403.14492v1 2403.14492v1 [cs.DS] , arXiv, March 2024

2024 arXiv
[19]

Thorup , Integer priority queues with decrease key in constant time and the single source shortest paths problem , Journal of Computer and System Sciences, 69 (2004), pp

M. Thorup , Integer priority queues with decrease key in constant time and the single source shortest paths problem , Journal of Computer and System Sciences, 69 (2004), pp. 330--353. doi : http://doi.org/10.1016/j.jcss.2004.04.003 10.1016/j.jcss.2004.04.003

2004 doi
[20]

Winkler , Proof of the squashed cube conjecture , Combinatorica, 3 (1983), pp

P. Winkler , Proof of the squashed cube conjecture , Combinatorica, 3 (1983), pp. 135--139. doi : http://doi.org/10.1007/BF02579350 10.1007/BF02579350

1983 doi

Pith tools

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

[1] [1]

F. N. Abu-Khzam , Maximum common induced subgraph parameterized by vertex cover , Information Processing Letters, 114 (2014), pp. 99--103. doi : http://doi.org/10.1016/j.ipl.2013.11.007 10.1016/j.ipl.2013.11.007

doi:10.1016/j.ipl.2013.11.007 2014

[2] [2]

F. N. Abu-Khzam, \'E . Bonnet, and F. Sikora , On the complexity of various parameterizations of common induced subgraph isomorphism , Theoretical Computer Science, 697 (2017), pp. 69--78. doi : http://doi.org/10.1016/j.tcs.2017.07.010 10.1016/j.tcs.2017.07.010

doi:10.1016/j.tcs.2017.07.010 2017

[3] [3]

Bollob \'a s, D

B. Bollob \'a s, D. Coppersmith, and M. Elkin , Sparse distance preservers and additive spanners , SIAM Journal on Discrete Mathematics, 19 (2006), pp. 1029--1055. doi : http://doi.org/10.1137/S0895480103431046 10.1137/S0895480103431046

doi:10.1137/s0895480103431046 2006

[4] [4]

Bergold, V

H. Bergold, V. Ir s i c , R. Lauff, J. Orthaber, M. Scheucher, and A. Wesolek , Subgraph-universal planar graphs for trees , Tech. Rep. http://arxiv.org/abs/10.48550/arXiv.2409.01678 2409.01678 [quant-ph] , arXiv, September 2024

arXiv doi:10.48550/arxiv.2409.01678

[5] [5]

Bunke, X

H. Bunke, X. Jiang, and A. Kandel , On the minimum common supergraph of two graphs , Computing, 65 (2000), pp. 13--25. doi : http://doi.org/10.1007/PL00021410 10.1007/PL00021410

work page doi:10.1007/pl00021410 2000

[6] [6]

Bodini , On the minimum size of a contraction-universal tree , in 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol

O. Bodini , On the minimum size of a contraction-universal tree , in 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 2573 of Lecture Notes in Computer Science, Springer, June 2002, pp. 25--34. doi : http://doi.org/10.1007/3-540-36379-3_3 10.1007/3-540-36379-3_3

work page doi:10.1007/3-540-36379-3_3 2002

[7] [7]

Bodwin , New results on linear size distance preservers , SIAM Journal on Computing, 50 (2021), pp

G. Bodwin , New results on linear size distance preservers , SIAM Journal on Computing, 50 (2021), pp. 662--673. doi : http://doi.org/10.1137/19M123662X 10.1137/19M123662X

doi:10.1137/19m123662x 2021

[8] [8]

Coppersmith and M

D. Coppersmith and M. Elkin , Sparse source-wise and pair-wise distance preservers , SIAM Journal on Discrete Mathematics, 20 (2006), pp. 463--501. doi : http://doi.org/10.1137/S0895480104445319 10.1137/S0895480104445319

work page doi:10.1137/s0895480104445319 2006