Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs

MaRDI QIDQ6324528zbMATH OpenFDO

Authors Shahin Kamali, Avery Miller, Kenny Zhang

Publication date 1 September 2019

Abstract: Graph burning is a simple model for the spread of social influence in networks. The objective is to measure how quickly a fire (e.g., a piece of fake news) can be spread in a network. The burning process takes place in discrete rounds. In each round, a new fire breaks out at a selected vertex and burns it. Meanwhile, the old fires extend to their neighbours and burn them. A burning schedule selects where the new fire breaks out in each round, and the burning problem asks for a schedule that burns all vertices in a minimum number of rounds, termed the burning number of the graph. The burning problem is known to be NP-hard even when the graph is a tree or a disjoint set of paths. For connected graphs, it has been conjectured that burning takes at most $lceilsqrtnceil$ rounds. We approach the algorithmic study of graph burning from two directions. First, we consider graphs with minimum degree $delta$. We present an algorithm that burns any graph of size $n$ in at most $sqrtfrac24ndelta+1$ rounds. In particular, for dense graphs with $deltainTheta(n)$, all vertices are burned in a constant number of rounds. More interestingly, even when $delta$ is a constant that is independent of the graph size, our algorithm answers the graph-burning conjecture in the affirmative by burning the graph in at most $lceilsqrtnceil$ rounds. Next, we consider burning graphs with bounded path-length or tree-length. These include many graph families including connected interval graphs and connected chordal graphs. We show that any graph with path-length $pl$ and diameter $d$ can be burned in $lceilsqrtd-1ceil+pl$ rounds. Our algorithm ensures an approximation ratio of $1+o(1)$ for graphs of bounded path-length. We introduce another algorithm that achieves an approximation ratio of $2+o(1)$ for burning graphs of bounded tree-length.

This page was built for publication: Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324528)