Publications

2025

1. 

   Burn and win

   Pradeesha Ashok, Sayani Das, Lawqueen Kanesh, and 3 more authors

   Theoretical Computer Science, 2025

   Abs DOI

   Given a graph G and an integer k, the Graph Burning problem asks whether the graph G can be burned in at most k rounds. Graph burning is a model for information spreading in a network, where we study how fast the information spreads in the network through its vertices. In each round, the fire is started at an unburned vertex, and fire spreads from every burned vertex to all its neighbors in the subsequent round, burning all of them and so on. The minimum number of rounds required to burn the whole graph G is called the burning number of G. Graph Burning is known to be W[1]-hard when parameterized by the burning number and para-NP-hard when parameterized by treewidth. In this paper, we observe that Graph Burning is a special case of the Non-Uniform k-Center problem and prove the following results:–We give an explicit algorithm for the Non-Uniform k-Center problem parameterized by treewidth, maximum radius, and total number of centers. We extend this to show that Graph Burning is FPT parameterized by treewidth and burning number. This also gives an FPT algorithm for Graph Burning parameterized by burning number for apex-minor-free graphs.–Y. Kobayashi and Y. Otachi [Algorithmica 2022] proved that the problem is FPT parameterized by distance to cographs and gave a double exponential time FPT algorithm parameterized by distance to split graphs. We improve these results partially and give an FPT algorithm for the problem parameterized by distance to cographs ∩ split graphs (threshold graphs) that runs in 2O(tln⁡t) time.–We design a kernel of exponential size for Non-Uniform k-Center problem and Graph Burning in trees.–Furthermore, we give an exact algorithm to find the burning number of a graph that runs in time 2nnO(1), where n is the number of vertices in the input graph.

2023

1. 

   Colouring a dominating set without conflicts: q-Subset Square Colouring

   V.P. Abidha, Pradeesha Ashok, Avi Tomar, and 1 more author

   Theoretical Computer Science, 2023

   Abs DOI

   The Square Colouring of a graph G refers to colouring of vertices of a graph such that any two distinct vertices which are at distance at most two receive different colours. In this paper, we initiate the study of a related colouring problem called the subset square colouring of graphs. Broadly, the subset square colouring of a graph studies the square colouring of a dominating set of a graph using q colours. Here, the aim is to optimize the number of colours used. This also generalizes the well-studied Efficient Dominating Set problem. We show that the q-Subset Square Colouring problem with q=2 is NP-hard even on planar bipartite graphs and the q-Subset Square Colouring problem is NP-hard even on bipartite graphs and chordal graphs. We further study the parameterized complexity of this problem when parameterized by a number of structural parameters. We further show bounds on the number of colours needed to subset square colour some graph classes.

2022

1. 

   Polynomial Kernels for Generalized Domination Problems

   Pradeesha Ashok, Rajath Rao, and Avi Tomar

   2022