The problem of Odd Cycle Transversal (OCT) in mixed graphs (i.e. some of the edges in the graph are directed) is as follows: Given a mixed graph D which has $l$ directed edges and a positive integer k, is it possible to delete at most k vertices to make D odd cycle free? We explored the fixed parameter tractability of the problem parameterized by k and l. This problem is an attempt to generalize the classical OCT. The complexity of the problem lies in between the classical OCT which is FPT and directed OCT which is W[1] hard (i.e no FPT algorithm exists) parameterized by k, which this makes the problem really interesting. We designed a FPT algorithm for the problem using the combinatorial gadget of tight sequence of important separators.
Link to the manuscript
(Published in WG 2021)
In this project, we addressed the following NP-hard problem: Given a digraph D and a positive integer k, is it possible to delete at most k vertices from D such that in the graph induced on the remaining set of vertices, there is at most one path between any pair of vertices? This problem is one of the directed counterparts of the undirected feedback vertex set problem. We want to hit cycles in the underlying undirected graph of D with some specific orientation in D. We studied the problem in digraphs with bounded independent number, local tournaments and in/out-tournaments and designed exact algorithms and kernels on these graph classes.
Link to the manuscript.
(accepted in IWOCA 2020)
(MSc Thesis)
In this survey, we studied three algorithmic techniques of subset convolution, principle of inclusion-exclusion and finite difference method of computing polynomial coefficients and saw their application on various problems that require computation over the subset lattice. We saw the application of subset convolution in designing algorithms for Steiner Tree problem, general partitioning problems and constructing Minimum Connected Spanning Hypergraphs, use of PIE for designing PSPACE algorithms for unweighted Steiner Tree and Channel Assignment Problem , and finite difference method for counting k–length paths and cycles in a graph. All the algorithms for the problems in the survey use the important idea of relaxation.
Link to the Report.
(B.Tech Thesis)
In this project, we defined and addressed the following problem: Given a grid based Road Network, a set of vehicles, their starting points, starting times and speeds and predefined paths, identify the maximum set of vehicles such that no collision takes place if they are allowed to move freely according to their paths and speeds. We proved the problem to be NP-hard by giving a reduction from Independent Set problem. We studied the structural properties of the grid based road network like condition of strong connectivity (which we found out can be checked in constant time) and shortest paths where we studied the possible structures and orientations of the shortest paths and gave a bound on the length of the largest shortest path in these graphs.
(Published in CCCG 2016)
In this project, we addressed the following problem: Given a set of strings over some finite alphabet, output the smallest length string (which we call as a superstring) such that all the strings in the set are substrings of the outputted string. This problem has a greedy heuristic algorithm designed by Ukkonen which performs really well in real life. Our aim was to come up with a subroutine with time as a budget parameter such that the solution outputted by the greedy algorithm can be modified and improved and the running time of our subroutine is a function of the budget. Such technique is called as turbo charging the greedy algorithm. We designed an exact algorithm for the shortest common superstring problem and used it to design a turbocharging procedure. In the limiting case, our turbocharging procedure turns into an exact algorithm. We proved that the string outputted by our modification procedure is at least as good as the solution of the greedy solution. We experimented with our modification procedure on a dataset but we could not provide any significant improvement over the greedy algorithm.
Link to Github page.
The purpose of this project was to understand how Backpropagation Algorithm works. I implemented the Backpropagation algorithm which used mini batch Gradient Descent with moment. Everything, from the gradient descent to the backpropagation has been implemented from scratch. I experimented with the implementation on a 3 layer (one hidden layer) Neural Network and managed to get an accuracy of $97.4\%$ on the submission dataset of kaggle in this very shallow network.
Link to the Kaggle kernel.