Research Projects

The dominating set problem is an optimization problem in graph theory that involves determining whether a graph has a dominating set of size at most k. This problem is NP-complete, even for bipartite graphs. Two variants of the dominating set problem are a star cover of G and a star partition of G. When restricted to triangle-free graphs, these problems become polynomially equivalent up to the optimum value, making them NP-complete. A close variant of STAR PARTITION has been studied in literature to generalize the maximum matching problem. A preliminary study of STAR PARTITION has several implications for STAR COVER. The researchers propose to continue studying these three problems by studying the relations among parameters underlying the problems, determining the computational complexity of the star cover and star partition problems for cographs, interval graphs, cobipartite graphs, K(1,4)-free split graphs, and other natural graph classes. They also plan to find better approximation algorithms for the problems on perfect graphs and/or its subclasses, prove better inapproximability results, study the problems in the FPT framework under different parameterizations, and design exact exponential time algorithms for the problems on natural graph classes. In conclusion, the dominating set problem is a crucial optimization problem in graph theory that can be applied to various graph classes.