2026-07-24T02:01:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18834 2024-03-06T11:02:41Z ddc:004 open_access

Approximation Algorithms and Lower Bounds for Graph Burning Lieskovský, Matej Sgall, Jiří Feldmann, Andreas Emil Graph Algorithms approximation Algorithms randomized Algorithms Graph Burning models information spreading in a given graph as a process such that in each step one node is infected (informed) and also the infection spreads to all neighbors of previously infected nodes. Formally, given a graph G = (V,E), possibly with edge lengths, the burning number b(G) is the minimum number g such that there exist nodes v_0,…,v_{g-1} ∈ V satisfying the property that for each u ∈ V there exists i ∈ {0,…,g-1} so that the distance between u and v_i is at most i. We present a randomized 2.314-approximation algorithm for computing the burning number of a general graph, even with arbitrary edge lengths. We complement this by an approximation lower bound of 2 for the case of equal length edges, and a lower bound of 4/3 for the case when edges are restricted to have length 1. This improves on the previous 3-approximation algorithm and an APX-hardness result. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matej Lieskovský and Jiří Sgall and Andreas Emil Feldmann 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.9 urn:nbn:de:0030-drops-188345 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.9 eng https://creativecommons.org/licenses/by/4.0/legalcode