2026-07-22T01:43:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24577 2025-12-16T14:01:03Z ddc:004 open_access

Deterministic Approximation Algorithm for Graph Burning Lieskovský, Matej Graph Algorithms Approximation Algorithms Graph Burning Graph Burning models a contagion spreading in a network as a process such that in each step one node is infected and also the infection spreads to all neighbors of previously infected nodes. Formally, the burning number b(G) of a given graph G = (V,E), possibly with edge lengths, is the minimum number g such that there exists a sequence of nodes v₁,…,v_g satisfying the property that for each w ∈ V there exists i ∈ {1,…,g} so that the distance between w and v_i is at most g-i. We present an elegant deterministic 2.314-approximation algorithm for the Graph Burning problem on general graphs with arbitrary edge lengths. This algorithm matches the approximation ratio of the previous randomized 2.314-approximation algorithm and improves on the previous deterministic 3-approximation algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matej Lieskovský 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.108 urn:nbn:de:0030-drops-245775 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.108 eng https://creativecommons.org/licenses/by/4.0/legalcode