Algorithms for Burning Schedule Reconfiguration Problem on Path Forests
摘要
Graph burning is a mathematical model that represents the spread of an influence. In each round, the fire spreads to the neighbors of previously burned vertices, and one additional unburned vertex is selected and burned. The burning schedule problem is a decision problem that determines whether a given graph can be burned using a given subset of vertices as burning sources. In this paper, we study the reconfiguration problem for burning schedule problems (BSRP), which involves determining whether, given a graph, a set of burning sources, and two feasible solutions of the burning schedule problem, one solution can be transformed into the other. We show that the burning schedule reconfiguration problem on path forests can be solved in polynomial time if there is one burning source in each path and also if there are two burning sources in a constant number of paths. Also we present an FPT algorithm for BSRP with input restrictions.