Research Projects

A broad spectrum of computational problems that arise in science and technology can be modeled using graphs due to their incredible modeling power. The outcomes of numerous experiments can be modeled using graphs with specific properties. However, these outcomes are susceptible to errors that influence the final results of these experiments. Naturally, one would look for a method to eliminate these errors and return the actual results from the collected results. This process is seen as a natural subclass of algorithmic graph problems called graph modification problems. The goal of these problems is to modify an input graph in some way to produce a graph with specific properties. The modifications can be vertex deletions, and edge modifications like completion, deletion, editing, etc. Graph modification problems have been extensively studied over the past four decades and found to be useful in a wide range of fields, like physical mapping of DNA, circuit design, and Gaussian elimination on sparse systems of linear equations. The major directions in the algorithmic study of every problem are to obtain the best (in terms of asymptotic time complexity) algorithms and better complexity lower bounds. The optimal complexity of a problem means the upper bound of the complexity achieved by an algorithm for the problem reaches the theoretical lower bound of that problem. Unfortunately, many important graph problems are computationally hard (NP-Hard), i.e., they cannot be solved in time polynomial in the size of the input graph, assuming the widely believed conjecture that P != NP. The various approaches to tackling NP-Hard problems are approximation, parameterized complexity, and kernelization. In a parameterized problem, an additional integer called parameter is also provided as an input, and the idea is to obtain algorithms such that the non-polynomial part of the running time is restricted to the parameter. Kernelization is a polynomial-time algorithm where the input is a parameterized problem that gives another instance of the same problem as output whose size is only a function of the parameter. In this proposal, our aim is bifold: 1) study graph modification problems to systematically place them on the complexity landscape according to their optimal complexity. 2) if a graph modification problem is computationally hard, then find the complexity of the problem in other paradigms like parameterized complexity, kernelization, and approximation. The paradigms being considered for this project are classical complexity, approximation, parameterized complexity, and kernelization and the graph modifications being considered are Seidel's switching and local complementation. For a graph G, the operation of switching a subset A of vertices is to reverse the adjacencies between A and V (G)\ A, whereas local complementation of G at a vertex v is the graph modification in which the graph induced by the neighbors of v is complemented.