Dhanyamol Antony

Dhanyamol Antony, L. Sunil Chandran, Anita Das et al.

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$.

Dhanyamol Antony, L. Sunil Chandran, Dalu Jacob et al.

Inversion of a directed graph $D$ with respect to a vertex subset $Y$ is the directed graph obtained from $D$ by reversing the direction of every arc whose endpoints both lie in $Y$. More generally, the inversion of $D$ with respect to a tuple $(Y_1, Y_2, \ldots, Y_\ell)$ of vertex subsets is defined as the directed graph obtained by successively applying inversions with respect to $Y_1, Y_2, \ldots, Y_\ell$. Such a tuple is called a \emph{decycling family} of $D$ if the resulting graph is acyclic. In the \textsc{$k$-Inversion} problem, the input consists of a directed graph $D$ and an integer $k$, and the task is to decide whether $D$ admits a decycling family of size at most $k$. Alon et al.\ (SIAM J.\ Discrete Math., 2024) proved that the problem is NP-complete for every fixed value of $k$, thereby ruling out XP algorithms, and presented a fixed-parameter tractable (FPT) algorithm parameterized by $k$ for tournament inputs. In this paper, we generalize their algorithm to a broader variant of the problem on tournaments and subsequently use this result to obtain an FPT algorithm for \textsc{$k$-Inversion} when the underlying undirected graph of the input is a block graph. Furthermore, we obtain an algorithm for \textsc{$k$-Inversion} on general directed graphs with running time $2^{O(\mathrm{tw}(k + \mathrm{tw}))} \cdot n^{O(1)}$, where $\mathrm{tw}$ denotes the treewidth of the underlying graph.

Dhanyamol Antony, L. Sunil Chandran, Anita Das et al.

Graph burning is a discrete-time process that models the propagation of information in a network. Initially, we have an undirected graph of unburned vertices. At each time step, an unburned vertex is chosen to burn; additionally, unburned vertices with at least one burned neighbor from the previous step also become burned. Once a vertex is burned, it remains burned for all future steps. The burning number of a graph is the minimum number of steps to burn all the vertices of the graph. The BURNING NUMBER PROBLEM asks whether the burning number of an input graph $G$ is at most $k$ or not. In this paper, we study the BURNING NUMBER PROBLEM both from an algorithmic and a structural viewpoint. The BURNING NUMBER PROBLEM is known to be NP-complete for interval graphs. Here, we prove that this problem is NP-complete even when restricted to connected proper interval graphs. The well-known burning number conjecture asserts that the burning number of a connected graph of order $n$ is at most $\lceil \sqrt{n}~\rceil$. In line with this conjecture, the upper and lower bounds of the burning number are well-studied for various graph classes. Here, we provide an improved upper bound for the burning number of connected $P_k$-free graphs and show that the bound is tight up to an additive constant of $1$. Finally, we study two variants of the problem: edge burning and total burning. We establish their relationship with the classical burning and evaluate the algorithmic complexity of these variants.