Hardness of Burning Number Problem on Regular Graphs

Dhanyamol Antony, L. Sunil Chandran, Anita Das, Shirish Gosavi, Dalu Jacob, Shashanka Kulamarva

arXivarxiv/2605.14730May 14, 2026cs.DSscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.14730
curl -X POST /api/v1/records/arxiv/2605.14730/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.14730/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'