2026-07-20T14:50:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23447 2025-10-02T12:55:24Z ddc:004 open_access

Tiling Random Regular Graphs Efficiently Diskin, Sahar Hoshen, Ilay Zhukovskii, Maksim Random regular graphs Tree tilings We show that for every ε > 0 there exists a sufficiently large d₀ ∈ ℕ such that for every d ≥ d₀, whp the random d-regular graph G(n,d) contains a T-factor for every tree T on at most (1-ε)d/log d vertices. This is best possible since, for large enough integer d, whp G(n,d) does not contain a ((1+ε)d)/(log d)-star-factor. Our method gives a randomised algorithm which whp finds said T-factor and whose expected running time is O(n^{1+o(1)}), as well as an efficient deterministic counterpart. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sahar Diskin and Ilay Hoshen and Maksim Zhukovskii 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.70 urn:nbn:de:0030-drops-234477 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.70 eng https://creativecommons.org/licenses/by/4.0/legalcode