Document Open Access Logo

Approximation Algorithms and Lower Bounds for Graph Burning

Authors Matej Lieskovský , Jiří Sgall , Andreas Emil Feldmann

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2023.9.pdf
  • Filesize: 0.77 MB
  • 17 pages

Document Identifiers

Author Details

Matej Lieskovský
  • Faculty of Mathematics and Physics, Computer Science Institute of Charles University, Prague, Czech Republic
Jiří Sgall
  • Faculty of Mathematics and Physics, Computer Science Institute of Charles University, Prague, Czech Republic
Andreas Emil Feldmann
  • Department of Computer Science, University of Sheffield, UK

Funding

  • Lieskovský, Matej: Partially supported by GAUK project 234723, and GA ČR project 19-27871X.
  • Sgall, Jiří: Partially supported by GA ČR project 19-27871X.

Acknowledgements

We are grateful to anonymous referees for detailed reviews and helpful comments.

Cite As Get BibTex

Matej Lieskovský, Jiří Sgall, and Andreas Emil Feldmann. Approximation Algorithms and Lower Bounds for Graph Burning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.9

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Graph Algorithms
  • approximation Algorithms
  • randomized Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon and Joel H. Spencer. The Probabilistic Method, Third Edition. Wiley, 2008. Google Scholar
  2. Stéphane Bessy, Anthony Bonato, Jeannette Janssen, Dieter Rautenbach, and Elham Roshanbin. Burning a graph is hard. Discrete Applied Mathematics, 232:73-87, 2017. URL: https://doi.org/10.1016/j.dam.2017.07.016.
  3. Anthony Bonato. A survey of graph burning. Contributions Discret. Math., 16(1):185-197, 2021. URL: https://cdm.ucalgary.ca/article/view/71194.
  4. Anthony Bonato, Jeannette Janssen, and Elham Roshanbin. How to burn a graph. Internet Mathematics, 12, July 2015. URL: https://doi.org/10.1080/15427951.2015.1103339.
  5. Anthony Bonato and Shahin Kamali. Approximation algorithms for graph burning. In T. V. Gopal and Junzo Watada, editors, Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13-16, 2019, Proceedings, volume 11436 of Lecture Notes in Computer Science, pages 74-92. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-14812-6_6.
  6. Anthony Bonato and Thomas Lidbetter. Bounds on the burning numbers of spiders and path-forests. Theor. Comput. Sci., 794:12-19, 2019. URL: https://doi.org/10.1016/j.tcs.2018.05.035.
  7. Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. ACM Trans. Algorithms, 16(4), June 2020. URL: https://doi.org/10.1145/3392720.
  8. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591884.
  9. Jesús García-Díaz, Julio César Pérez-Sansalvador, Lil María Xibai Rodríguez-Henríquez, and José Alejandro Cornejo-Acosta. Burning graphs through farthest-first traversal. IEEE Access, 10:30395-30404, 2022. URL: https://doi.org/10.1109/ACCESS.2022.3159695.
  10. Tanmay Inamdar and Kasturi R. Varadarajan. Non-uniform k-center and greedy clustering. In Artur Czumaj and Qin Xin, editors, 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT, volume 227 of LIPIcs, pages 28:1-28:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.SWAT.2022.28.
  11. Xinrui Jia, Lars Rohwedder, Kshiteej Sheth, and Ola Svensson. Towards non-uniform k-center with constant types of radii. In Karl Bringmann and Timothy Chan, editors, 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, pages 228-237. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977066.16.
  12. Shahin Kamali, Avery Miller, and Kenny Zhang. Burning two worlds. In Alexander Chatzigeorgiou, Riccardo Dondi, Herodotos Herodotou, Christos A. Kapoutsis, Yannis Manolopoulos, George A. Papadopoulos, and Florian Sikora, editors, SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20-24, 2020, Proceedings, volume 12011 of Lecture Notes in Computer Science, pages 113-124. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-38919-2_10.
  13. Anjeneya Swami Kare and I. Vinod Reddy. Parameterized algorithms for graph burning problem. In Charles J. Colbourn, Roberto Grossi, and Nadia Pisanti, editors, Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23-25, 2019, Proceedings, volume 11638 of Lecture Notes in Computer Science, pages 304-314. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-25005-8_25.
  14. Yasuaki Kobayashi and Yota Otachi. Parameterized complexity of graph burning. Algorithmica, 84(8):2379-2393, 2022. URL: https://doi.org/10.1007/s00453-022-00962-8.
  15. Matej Lieskovský and Jirí Sgall. Graph burning and non-uniform k-centers for small treewidth. In Approximation and Online Algorithms - 20th International Workshop, WAOA 2022, Potsdam, Germany, September 8-9, 2022, Proceedings, volume 13538 of Lecture Notes in Computer Science, pages 20-35. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-18367-6_2.
  16. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. URL: https://doi.org/10.1017/CBO9780511813603.
  17. Debajyoti Mondal, N. Parthiban, V. Kavitha, and Indra Rajasingh. APX-hardness and approximation for the k-burning number problem. In Ryuhei Uehara, Seok-Hee Hong, and Subhas C. Nandy, editors, WALCOM: Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 - March 2, 2021, Proceedings, volume 12635 of Lecture Notes in Computer Science, pages 272-283. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-68211-8_22.
  18. Debajyoti Mondal, Angelin Jemima Rajasingh, N. Parthiban, and Indra Rajasingh. APX-hardness and approximation for the k-burning number problem. Theor. Comput. Sci., 932:21-30, 2022. URL: https://doi.org/10.1016/j.tcs.2022.08.001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact