2026-07-21T14:16:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24123 2025-11-12T13:33:20Z ddc:004 open_access

Isometric-Universal Graphs for Trees Baucher, Edgar Dross, François Gavoille, Cyril tree forest isometric subgraph universal graph distance-preserving 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Edgar Baucher and François Dross and Cyril Gavoille 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.16 urn:nbn:de:0030-drops-241237 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode