Seminars
View all Seminars | Download ICal for this eventHardness, Algorithmic and Structural Results on Graph Burning and CD-Coloring
Series: Ph.D. Colloquium
Speaker: Shirish Gosavi, Ph.D (Engg.) student, Dept. of CSA, IISc
Date/Time: Jun 25 16:00:00
Location: CSA Lecture Hall (Room No. 112, Ground Floor)
Faculty Advisor: Prof. Sunil Chandran L
Abstract:
Graph-theoretic models play a central role in understanding complex networks arising in communication systems, social interactions, biological processes, distributed computing etc. A fundamental objective in graph theory is to determine how structural restrictions on graphs influence the computational complexity of optimization and decision problems. This dissertation investigates this theme through two research directions: Graph Burning and CD-Coloring. The work develops new structural insights, hardness results and efficient algorithms for these problems on some important graph classes.
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 required to burn all the vertices of the graph.
The burning number problem (BNP) asks whether the burning number of an input graph G is at most k or not. BNP is known to be NP-complete even on restricted graph classes such as path forests. We have shown that BNP is NP-complete on connected cubic graphs and d-regular graphs (d ? 3) and is moreover APX-hard under this restriction. In addition, we have also shown that the problem is NP-complete for 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 ceil(sqrt(n)). In line with this conjecture, we have provided an improved upper bound for the burning number of connected graphs that do not have induced paths on k vertices. We also studied two variants of the problem: Edge Burning and Total Burning and have established their relationship with the classical graph burning.
CD-Coloring incorporates the flavors of two classic problems in graph theory, namely, domination and coloring. A proper vertex coloring of a connected graph G is said to be a cd-coloring, if for each color class, all the vertices in that color class are dominated by one vertex (there can be more than one such vertex). The minimum integer k for which there exists a cd-coloring of G using k colors is called the -cd-chromatic number- of G. The -total domination number- of G is defined to be the minimum integer k such that G has a total dominating set of size k. A subset of vertices, S, is said to be a -separated cluster- if no two vertices in S lie at a distance exactly 2 in G. The -separated cluster number- of G is defined to be the maximum integer k such that G has a separated cluster of size k. We have contributed to the literature connecting cd-coloring with total domination and separated cluster as follows.
It is known that deciding the total domination number is NP-complete for cubic graphs and triangle-free subcubic graphs. We have strengthened this result by proving that both the problems, cd-coloring and total domination, are NP-complete, for triangle-free d-regular graphs (d ? 3). Analogous to the well-known notion of -perfectness-, we have introduced the notion of -cd-perfectness- and have proved a sufficient condition for a graph G to be cd-perfect. Our sufficient condition turns out to be necessary for certain graph classes (like triangle-free graphs).