Hardness of Burning Number Problem on Regular Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913129009512448 |
|---|---|
| author | Antony, Dhanyamol Chandran, L. Sunil Das, Anita Gosavi, Shirish Jacob, Dalu Kulamarva, Shashanka |
| author_facet | Antony, Dhanyamol Chandran, L. Sunil Das, Anita Gosavi, Shirish Jacob, Dalu Kulamarva, Shashanka |
| contents | The Burning Number Problem (BNP) models the spread of information or contagion in a network through a discrete-time process on a graph. At each step, one new vertex is selected as a burning source, while fire simultaneously spreads from previously burned vertices to their neighbors. The burning number of a graph is the minimum number of steps required to burn all vertices. The decision version asks whether the burning number is at most a given integer $k$. BNP is known to be NP-complete even on restricted graph classes such as path forests. We study BNP on connected regular graphs, a natural and previously unexplored graph class. We prove that BNP is NP-complete on connected cubic graphs, and moreover APX-hard under this restriction. We further show that BNP remains APX-hard on connected $d$-regular graphs for every fixed $d \geq 4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_14730 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hardness of Burning Number Problem on Regular Graphs Antony, Dhanyamol Chandran, L. Sunil Das, Anita Gosavi, Shirish Jacob, Dalu Kulamarva, Shashanka Data Structures and Algorithms Discrete Mathematics Combinatorics The Burning Number Problem (BNP) models the spread of information or contagion in a network through a discrete-time process on a graph. At each step, one new vertex is selected as a burning source, while fire simultaneously spreads from previously burned vertices to their neighbors. The burning number of a graph is the minimum number of steps required to burn all vertices. The decision version asks whether the burning number is at most a given integer $k$. BNP is known to be NP-complete even on restricted graph classes such as path forests. We study BNP on connected regular graphs, a natural and previously unexplored graph class. We prove that BNP is NP-complete on connected cubic graphs, and moreover APX-hard under this restriction. We further show that BNP remains APX-hard on connected $d$-regular graphs for every fixed $d \geq 4$. |
| title | Hardness of Burning Number Problem on Regular Graphs |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2605.14730 |