| dc.description.abstract | In the thesis, we mainly discuss variants of two well-studied graph theoretical problems - vertex deletion problem and graph coloring problem - both have been used to tackle many real-world problems in diverse fields.
Vertex deletion problems form a core topic in algorithmic graph theory with many applications. Typically, the objective of a vertex deletion problem is to delete the minimum number of vertices so that the remaining graph satisfies some property. Many classic optimization problems like Maximum Clique, Maximum Independent Set, and Vertex cover are examples of vertex deletion problems. In the first part of the thesis, we study popular vertex deletion problems called Cluster Vertex Deletion and its generalization s-Club Cluster Vertex Deletion, both being important in the context of graph-based data clustering. A cluster is often viewed as a dense subgraph (often a clique), and partitioning a graph into such clusters is one of the main objectives of graph-based data clustering. However, to account for the errors introduced during the construction of the network, the clusters of certain networks may be retrieved by making a small number of modifications such as deleting some vertices.
Given a graph G, the objective of Cluster Vertex Deletion (CVD) is to delete a minimum number of vertices so that the remaining graph is a set of disjoint cliques. We focus on the polynomial-time solvability of CVD on special classes of graphs. Chordal graphs (graphs with no induced cycle of length greater than 3) are a well-studied class of graphs with many applications in algorithmic graph theory. Though polynomial-time algorithms for certain subclasses of chordal graphs such as interval graphs, block graphs, and split graphs are known, the computational complexity of CVD on chordal graphs remains unknown. We study CVD on well-partitioned chordal graphs, another subclass of chordal graphs that generalizes split graphs, which is introduced as a tool for narrowing down complexity gaps for problems that are hard on chordal graphs and easy on split graphs.
In many applications, the equivalence of cluster and clique is too restrictive. For example, in protein networks where proteins are the vertices and the edges indicate the interaction between the proteins, a more appropriate notion of clusters may have a diameter of more than 1. Therefore researchers have defined the notion of s-clubs. An s-club is a graph with diameter at most s. The objective of s-Club Cluster Vertex Deletion (s-CVD) is to delete the minimum number of vertices from the input graph so that each connected component of the resultant graph is an s-club. We propose a polynomial-time algorithm for (s-CVD) on trapezoid graphs, a class of intersection graphs. To the best of our knowledge, our result provides the first polynomial-time algorithm for Cluster Vertex Deletion on trapezoid graphs. We also provide a faster algorithm for s-CVD on interval graphs. For each s >=1, we give an O(n(n+m))-time algorithm for s-CVD on interval graphs with n vertices and m edges. We also prove some hardness results for s-CVD on planar bipartite graphs, split graphs, and well-partitioned chordal graphs for each s >=2.
Graph coloring has diverse applications and is still a prominent research area to tackle many practical problems by simulating them as coloring the vertices or edges of a graph subject to some constraints. In the second part of the thesis, we discuss a variant of the graph coloring problem. Efficient and scalable implementation of parallel algorithms on multiprocessor architectures with multiple memory banks requires simultaneous access to the data items. Such ''conflict-free'' access to parallel memory systems and other applied problems motivate the study of rainbow coloring of a graph, in which there is a fixed template T (or a family of templates), and one seeks to color the vertices of an input graph G with as few colors as possible, so that each copy of T in G is rainbow colored, i.e., has no two vertices the same color. We call such coloring a template-driven rainbow coloring and study the rainbow coloring of proper interval graphs (as hosts) for cycle templates.
Generalizing the perfect graphs, Gy\'arf\'as introduced the concept of a Chi-bounded class of graphs. A graph class is said to be Chi-bounded if the chromatic number of the graphs in the class can be bounded by a function of their clique number. In the third part of the thesis, we study the Chi-boundedness of squares of bipartite graphs and their subclasses. We also propose an approximation algorithm for the proper coloring of squares of convex bipartite graphs. | en_US |
