Improved algorithms for burning graph families
Loading...
Date
2022-03-14
Authors
Shabanijou, Mohammadmasoud
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In the graph burning problem, the input is an undirected, unweighted, finite, and simple graph. A fire starts at a vertex at each round, and when a particular vertex is burned, all of its adjacent vertices are burned in the next round. We assume that the rounds are synchronous and discrete. At each round, one new fire can start in a new vertex. The goal is to select the vertices at which fires are started so that all vertices are burned as quickly as possible. Finding an optimal burning sequence is known to be NP-hard and the problem remains NP-hard even for simple graph families such as trees or a set of disjoint paths. The best approximation algorithm for general graphs has an approximation factor of 3.
In this thesis, we investigate this problem on different graph families of sparse graphs, and in particular, we look at cactus graphs and melon graphs and study algorithms that aim to burn these graphs as quickly as possible. For both graph families, we show that the problem is NP-complete, and provide approximation algorithms with approximation factors smaller than 3.
Description
Keywords
Graph burning problem, Approximation algorithms, NP-completeness, Algorithm Design