Graph Burning is a model that captures the spread of information in a network. Here, in each round, the fire starts at an unburned vertex called fire source, and in every subsequent round, fire spreads from every burned vertex to all of its unburned neighbors. Given a graph \(G=(V,E)\) and an integer b, the Graph Burning problem asks whether all vertices of G can be burned in b rounds. The optimization version of the Graph Burning problem asks to find the minimum b, such that G can be burned in b rounds. The Graph Burning problem is known to be NP-complete even for disjoint paths. Further, it is known that the Graph Burning problem is W[1]-hard when parameterised by b and the optimization version of the Graph Burning problem is known to be APX-hard. In this paper, we give a PTAS for the Graph Burning problem, for a specific graph class and also study the parameterised complexity of the problem under many parameterisations.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Burning Path-Like and Clique-Like Graphs

  • Radhika Aggarwal,
  • Pradeesha Ashok,
  • Dhairya Gupta

摘要

Graph Burning is a model that captures the spread of information in a network. Here, in each round, the fire starts at an unburned vertex called fire source, and in every subsequent round, fire spreads from every burned vertex to all of its unburned neighbors. Given a graph \(G=(V,E)\) and an integer b, the Graph Burning problem asks whether all vertices of G can be burned in b rounds. The optimization version of the Graph Burning problem asks to find the minimum b, such that G can be burned in b rounds. The Graph Burning problem is known to be NP-complete even for disjoint paths. Further, it is known that the Graph Burning problem is W[1]-hard when parameterised by b and the optimization version of the Graph Burning problem is known to be APX-hard. In this paper, we give a PTAS for the Graph Burning problem, for a specific graph class and also study the parameterised complexity of the problem under many parameterisations.