Burn and win

Given a graph G and an integer k, the Graph Burning problem asks whether the graph G can be burned in at most k rounds. Graph burning is a model for information spreading in a network, where we study how fast the information spreads in the network through its vertices. In each round, the fire is started at an unburned vertex, and fire spreads from every burned vertex to all its neighbors in the subsequent round, burning all of them and so on. The minimum number of rounds required to burn the whole graph G is called the burning number of G. Graph Burning is known to be W[1]-hard when parameterized by the burning number and para-NP-hard when parameterized by treewidth. In this paper, we observe that Graph Burning is a special case of the Non-Uniform k-Center problem and prove the following results: – We give an explicit algorithm for the Non-Uniform k-Center problem parameterized by treewidth, maximum radius, and total number of centers. We extend this to show that Graph Burning is FPT parameterized by treewidth and burning number. This also gives an FPT algorithm for Graph Burning parameterized by burning number for apex-minor-free graphs. – Y. Kobayashi and Y. Otachi [Algorithmica 2022] proved that the problem is FPT parameterized by distance to cographs and gave a double exponential time FPT algorithm parameterized by distance to split graphs. We improve these results partially and give an FPT algorithm for the problem parameterized by distance to cographs ∩ split graphs (threshold graphs) that runs in 2 O ( t ln ⁡ t ) time. – We design a kernel of exponential size for Non-Uniform k-Center problem and Graph Burning in trees. – Furthermore, we give an exact algorithm to find the burning number of a graph that runs in time 2 n n O ( 1 ), where n is the number of vertices in the input graph.

Authors

• Pradeesha Ashok
• Sayani Das
• Lawqueen Kanesh
• Saket Saurabh
• Avi Tomar
• Shaily Verma

Keywords

• Burning number
• Non-uniform k-center
• Fixed-parameter tractability
• Treewidth
• Apex-minor free graphs
• Threshold graphs