My name is Ajinkya Gaikwad and I am a PhD student at the Indian Institute of Science Education and Research, Pune. Currently, I am working under the supervision of Dr. Soumen Maity in the field of parameterized complexity theory.

My primary interest is to address computationally hard problems which are characterization of real life problems and deal with them using tools of parameterized complexity theory. Parameterized complexity theory is a branch of complexity theory that deals with NP-hard problems to address the issue of classification of such problems according to their difficulty with respect to different input and output parameters. A parameterized problem has an input instance x as well as a parameter k which is sufficiently small compare to the size of the input instance. A parameterized problem is FPT (fixed parameter tractable) if there exists an algorithm which correctly decides whether the input instance of the given problem is a yes or no instance in time which is polynomial in the size of the input instance but possibly exponential in k. Certain parameterized problems are unlikely to be fixed parameter tractable; there seems to be different levels of hardness in parameterized complexity theory. Downey and Fellows introduced the W-hierarchy in an attempt to classify parameterized problems according to their hardness.

Our main focus is classifying different NP-hard problems parameterized by natural as well as structral parameters into computational complexity classes. Until now in this project, we have worked on exploring the parameterized complexity of the following computational problems: defensive and offensive alliances in graphs; the satisfactory partition problem; the harmless set problem; locally and globally minimal defensive alliances; upper edge dominating set problem; Edge deletion to bounded size connected components; minimal feedback vertex set problem.