Research Projects

Research Paradigm: One of the greatest achievements in theoretical computer science is the development of the theory of NP-completeness. Towards this, researchers design approximation algorithms (AA), which guarantee reasonable bounds on the quality of the solutions on all inputs. Another powerful framework is parameterized complexity (PC), where the input comes with an additional parameter $k \in \mathbb{N}$, which describes a property of the input I and is typically assumed to be small in practical applications. The aim is to restrict the exponential part of the running time to this parameter and have only a polynomial dependence on the input size |I|. A parameterized problem is said to be fixed-parameter tractable (FPT) if it admits an algorithm (called FPT algorithms) computing an optimal solution in time f(k).|I|^{O(1)}, where f is some computable function that depends solely on k. Another integral concept in PC is that of kernelization. It would produce equivalent instances of small size for instances with small parameters, which may be solved efficiently. Over the years, researchers have studied several problems in the domains of AA and PC in parallel. It naturally led to the study of the problem in the recently developed field of FPT approximation (FPT-A), where the above two paradigms are combined. It allowed for intriguing discoveries in the intersection of the two worlds. A brief research overview is as follows. In the k-median clustering problem, the task is to partition data into k clusters by minimizing sum of distances between each point and the median of its assigned cluster. We explore exact and parameterized algorithms for k-median and its constrained variants where clusters must satisfy specific capacity requirements. Further examine fairness in clustering, where the goal is to ensure equitable representation of protected attributes (e.g. gender, race) across clusters from an FPT-A perspective. The project also extends fairness analysis to classical graph problems. One such problem is Fair Hitting Set problem, a generalization of the classical Hitting Set problem, where given universe U, a family F of subsets of U, a non negative integer k, the input additionaly contains a family B of subsets of U, where each subset in B can be thought of as group of elements of the same type. We want to find a set S \subseteq U of size k that hits all sets of F and does not contain too many elements of each type. We use advanced tools like matroids and representative sets to analyze its PC. For future we propose exploring PC of constraint clustering and fair variants of other graph problem, such as Fair Odd Cycle Transversal, where given G= (V, E),k, positive integer l, the task is to find whether there exists S\subseteq V(G) of size at most k such that remaining graph is bipartite and for every v in V(G),v has atmost l neighbors in S.These fair variant remain largely unexplored in comparison to its classical counterparts