Bi-Weekly Talk: Katharina Eickhoff: Integer Programming Formulations for the Burning Number Problem

Wednesday, April 07, 2021, 10:30am


Speaker: Katharina Eickhoff



The Burning Number (Bonato et al.) indicates the minimal number of steps needed to inflame an undirected graph. In each step, the fire spreads to all neighbors of burning vertices and an arbitrarily chosen vertex is set on fire. This problem is known to be NP-hard.
We present two integer programming formulations for this problem and compare them. In a computational study we analyse the difference between the IP's objective function value and its relaxation and add further constraints. Additionally, we examine the runtimes for generating the contraints as well as the runtimes for solving the IPs/LPs.