2026-08-17T16:19:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7411 2024-03-06T10:40:33Z ddc:004 open_access

Near-Optimal Induced Universal Graphs for Bounded Degree Graphs Abrahamsen, Mikkel Alstrup, Stephen Holm, Jacob Knudsen, Mathias Bæk Tejs Stöckel, Morten Adjacency labeling schemes Bounded degree graphs Induced universal graphs Distributed computing A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U. We give upper and lower bounds for the size of induced universal graphs for the family of graphs with n vertices of maximum degree D. Our new bounds improve several previous results except for the special cases where D is either near-constant or almost n/2. For constant even D Butler [Graphs and Combinatorics 2009] has shown O(n^(D/2)) and recently Alon and Nenadov [SODA 2017] showed the same bound for constant odd D. For constant D Butler also gave a matching lower bound. For generals graphs, which corresponds to D = n, Alon [Geometric and Functional Analysis, to appear] proved the existence of an induced universal graph with (1+o(1)) \cdot 2^((n-1)/2) vertices, leading to a smaller constant than in the previously best known bound of 16 * 2^(n/2) by Alstrup, Kaplan, Thorup, and Zwick [STOC 2015]. In this paper we give the following lower and upper bound of binom(floor(n/2))(floor(D/2)) * n^(-O(1)) and binom(floor(n/2))(floor(D/2)) * 2^(O(sqrt(D log D) * log(n/D))), respectively, where the upper bound is the main contribution. The proof that it is an induced universal graph relies on a randomized argument. We also give a deterministic upper bound of O(n^k / (k-1)!). These upper bounds are the best known when D <= n/2 - tilde-Omega(n^(3/4)) and either D is even and D = omega(1) or D is odd and D = omega(log n/log log n). In this range we improve asymptotically on the previous best known results by Butler [Graphs and Combinatorics 2009], Esperet, Arnaud and Ochem [IPL 2008], Adjiashvili and Rotbart [ICALP 2014], Alon and Nenadov [SODA 2017], and Alon [Geometric and Functional Analysis, to appear]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikkel Abrahamsen and Stephen Alstrup and Jacob Holm and Mathias Bæk Tejs Knudsen and Morten Stöckel 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.128 urn:nbn:de:0030-drops-74114 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.128 eng https://creativecommons.org/licenses/by/3.0/legalcode